<!DOCTYPE html><html lang="en">
      
      
        
    
    
    
    

      
      
      <head>
        <meta charset="utf-8">
        <meta name="format-detection" content="telephone=no">  
        
        <title>Lecture 11: Relations, Partial Orders, and Scheduling | Video Lectures | Mathematics for Computer Science | Electrical Engineering and Computer Science | MIT OpenCourseWare</title>
    <!-- Begin Automatic Metadata Insertion -->
    <meta content="6-042j-mathematics-for-computer-science-fall-2010" name="WT.cg_n">
    <meta content="Lecture 11: Relations, Partial Orders, and Scheduling" name="WT.cg_s">
    <meta content="Covers definitions and examples of basic relations, equivalence classes, Hasse diagrams and topological sorts, as well as other topics." name="Description">
    <meta content="Leighton, Tom" name="Author">
    <meta content="Dijk, Marten van " name="Author">
    <meta content="6.042J,6.042,18.062J,18.062,relations,partial orders,poset,Hasse diagram,total order,topological sort,parallel task scheduling,Dilworth's lemma,reflexive,antisymmetric,transitive,symmetric,Computer Science,Probability and Statistics,Applied Mathematics,Discrete Mathematics" name="keywords">
    <meta content="6.042J Mathematics for Computer Science | Lecture 11: Relations, Partial Orders, and Scheduling" name="Search_Display">
    <meta content="Computer Science" itemprop="about">
    <meta content="Probability and Statistics" itemprop="about">
    <meta content="Applied Mathematics" itemprop="about">
    <meta content="Discrete Mathematics" itemprop="about">
    <!-- End Automatic Metadata Insertion -->

	<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/grid.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/base.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/menu.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/jquery.bubblepopup.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/search.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/courses.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/courses_new.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/jquery.jscrollpane.css">
<link title="default" rel="stylesheet" type="text/css" href="../../../common/styles/media_tabs.css">
	<link href="../../../common/xml/ocwcc.rdf" type="application/rdf+xml" rel="metadata">
	<link rel="canonical" href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-11-relations-partial-orders-and-scheduling/">
	<link rel="apple-touch-icon" href="../../../common/images/apple-touch-icon.png">
	
	
      
	
	<script type="text/javascript" src="../../../common/scripts/jquery.js"></script>
	<script type="text/javascript" src="../../../common/scripts/ocw-media-utils-offline.js"></script>
	<script type="text/javascript" src="../../../common/scripts/ocw-offline.js"></script>
	<script type="text/javascript" src="../../../common/scripts/jquery.bubblepopup.min.js"></script>
	<script type="text/javascript" src="../../../common/scripts/jquery-ui.min.js"></script>
	<script type="text/javascript" src="../../../common/scripts/jquery.jscrollpane.min.js"></script>
	<script type="text/javascript" src="../../../common/scripts/expandy.js"></script>
	<script type="text/javascript" src="../../../common/scripts/bubble-popup-offline.js"></script>
	
	
	
    <script type="text/javascript">
      $(document).ready(function() {
        $("#tabs").tabs();
        IpadScroller();
      });
    </script>
    
    
    
    
    
    
      
       
		 

        
        
        

        
        
        
        
        
        
        
        
        
      </head>
    <body itemscope itemtype="http://schema.org/WebPage">
        
	

        <header id="top">
			<div id="grid">
				
				
					
<div id="portletwrapper-6f63772e746f70706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a736974652d686561646572" class="portletWrapper kssattr-portlethash-6f63772e746f70706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a736974652d686561646572">
<div class="portletStaticText portlet-static-site-header">
<!--googleoff: index-->
<div class="grid_6 alpha" id="banner"><a href="https://ocw.mit.edu/"><img src="../../../common/images/ocw_mast.png" class="logo" alt="MIT OpenCourseWare, Massachusetts Institute of Technology"></a></div>
<div class="grid_6 omega" id="subscribe">
<aside class="module" aria-label="Connect with OCW">
<table class="social">
    <tbody>
        <tr>
            <td class="socialbutton"><a aria-label="Subscribe to the OCW Newsletter" href="https://ocw.mit.edu/subscribe/index.htm?utm_source=header"><img src="../../../common/images/trans.gif" alt="An icon depicting an envelope.">Subscribe to the OCW Newsletter</a></td>
            <td>
<a aria-label="Facebook" href="https://facebook.com/mitocw"><img src="../../../common/images/icon_fb.png" alt="Click to visit our Facebook page."></a>  <a aria-label="Instagram" href="https://www.instagram.com/mitocw/"><img src="https://ocw.mit.edu/images/icon_ig.png" alt="Click to visit our Instagram page."></a> <a aria-label="Twitter" href="https://twitter.com/mitocw"><img src="https://ocw.mit.edu/images/icon_twitter.png" alt="Click to visit our Twitter feed."></a><a aria-label="YouTube" href="https://www.youtube.com/mitocw" style="font-size: 12.208px;"><img src="https://ocw.mit.edu/images/icon_yt.png" alt="Click to visit our YouTube page."></a><span style="font-size: 12.208px;">   </span><a aria-label="Open Matters blog on WordPress" href="https://www.ocw-openmatters.org/" style="font-size: 12.208px;"><img src="https://ocw.mit.edu/images/icon_wp.png" alt="Click to visit our blog on WordPress."></a>
</td>
        </tr>
    </tbody>
</table>
</aside><nav aria-label="Help Links" class="helplinks">     <a aria-label="OCW Site Help" href="https://ocw.mit.edu/help">Help</a><span aria-hidden="true">|</span>     <a href="../../../common/about/contactus.htm">Contact Us</a>   </nav>
</div>
<div class="clear"> </div>
<!--googleon: index-->
</div>

</div>

<div id="portletwrapper-6f63772e746f70706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a6d6567612d6d656e75" class="portletWrapper kssattr-portlethash-6f63772e746f70706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a6d6567612d6d656e75">
<div class="portletStaticText portlet-static-mega-menu"><div><nav id="mega" class="grid_8 alpha" aria-label="Site">
<ul id="menu" role="presentation">
    <li id="menu_home">
<a href="https://ocw.mit.edu/" aria-label="Homepage"><img src="../../../common/images/top-nav_home.png" class="home_icon" alt="Click for site home page."></a><!-- Begin Home Item -->
</li>
    <!-- End Home Item -->
    <li id="drop_1" aria-label="Find Courses">
<a href="#" aria-hidden="true">FIND COURSES</a><!-- Begin 5 columns Item -->
    <div class="dropdown_5columns-a mega-courses">
    <div class="col_1a">
    <div class="row_1a">
<nav aria-labelledby="mm-find-courses-by">     <span id="mm-find-courses-by" class="nav" aria-hidden="true">Find courses by:</span>
    <ul class="find_by" role="presentation">
        <li><a href="https://ocw.mit.edu/courses/find-by-topic/">Topic</a></li>
        <li><a href="https://ocw.mit.edu/courses/find-by-number/">MIT Course Number</a></li>
        <li><a href="https://ocw.mit.edu/courses/find-by-department/">Department</a></li>
    </ul>
    </nav>     <nav aria-labelledby="mm-collections">     <span id="mm-collections" class="nav" aria-hidden="true">Collections</span>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/courses/new-courses/">New Courses</a></li>
        <li><a href="https://ocw.mit.edu/courses/most-visited-courses/">Most Visited Courses</a></li>
        <li><a href="https://ocw.mit.edu/courses/ocw-scholar/">OCW Scholar Courses</a></li>
        <li><a href="https://ocw.mit.edu/courses/audio-video-courses/">Audio/Video Lectures</a></li>
        <li><a href="https://ocw.mit.edu/courses/online-textbooks/">Online Textbooks</a></li>
        <li><a href="https://ocw.mit.edu/resources/">Supplemental Resources</a></li>
        <li><a href="https://ocw.mit.edu/high-school/">OCW Highlights for High School</a></li>
        <li><a href="https://ocw.mit.edu/courses/mitx-related-courseware/">MITx &amp; Related OCW Courses</a></li>
        <li><a href="https://ocw.mit.edu/courses/mit-open-learning-library/">MIT Open Learning Library</a></li>
    </ul>
    </nav>     <nav class="col_1b" aria-labelledby="mm-translated-courses">     <span id="mm-translated-courses" class="nav" aria-hidden="true" style="line-height: 1.3;">Cross-Disciplinary Topic Lists</span>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/courses/energy-courses">Energy</a></li>
        <li><a href="https://ocw.mit.edu/courses/entrepreneurship">Entrepreneurship</a></li>
        <li><a href="https://ocw.mit.edu/courses/environment-courses">Environment</a></li>
        <li><a href="https://ocw.mit.edu/courses/intro-programming">Introductory Programming</a></li>
        <li><a href="https://ocw.mit.edu/courses/life-sciences">Life Sciences</a></li>
        <li><a href="https://ocw.mit.edu/courses/transportation-courses">Transportation</a></li>
    </ul>
    </nav>
</div>
    <div class="row_1b"><nav aria-labelledby="mm-cross-disciplinary-topic-lists">     <span id="mm-cross-disciplinary-topic-lists" class="nav" aria-hidden="true">Translated Courses</span>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/courses/translated-courses/traditional-chinese" aria-label="Traditional Chinese">繁體字 / Traditional Chinese</a></li>
        <li><a href="https://ocw.mit.edu/courses/translated-courses/turkish" aria-label="Turkish">Türkçe / Turkish</a></li>
        <li><a href="https://ocw.mit.edu/courses/translated-courses/korean" aria-label="Korean">(비디오)한국 / Korean</a></li>
    </ul>
    </nav></div>
    </div>
    </div>
    </li>
    <li id="drop_2">
<a href="#" aria-label="For Educators">For Educators</a>
    <div class="dropdown_1column-a" style="width: 270px;"><nav aria-labelledby="mm-find-courses-by">
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/educator/chalk-radio-podcast">Chalk Radio Podcast</a></li>
        <li><a href="https://ocw.mit.edu/educator/">OCW Educator Portal</a></li>
    </ul>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/courses/instructor-insights/">Instructor Insights by Department</a></li>
        <li><a href="https://openlearning.mit.edu/campus/digital-innovations/">Residential Digital Innovations </a></li>
    </ul>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/high-school/">OCW Highlights for High School</a></li>
    </ul>
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/educator/additional-resources/">Additional Resources</a></li>
    </ul>
    </nav></div>
    </li>
    <li id="drop_3">
<a href="#" aria-hidden="true">Give Now</a>
    <div class="dropdown_1column-a"><nav class="col_1" aria-label="Donate">
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/give/">Make a Donation</a></li>
        <li><a href="https://ocw.mit.edu/give/why-give/">Why Give?</a></li>
        <li><a href="https://ocw.mit.edu/give/our-supporters/">Our Supporters</a></li>
        <li><a href="https://ocw.mit.edu/give/other-ways-to-contribute/">Other Ways to Contribute</a></li>
        <li><a href="https://ocw.mit.edu/support/">Become a Corporate Sponsor</a></li>
    </ul>
    </nav></div>
    </li>
    <li id="drop_4">
<a href="#" aria-hidden="true">About</a>
    <div class="dropdown_1column-a"><nav class="col_1" aria-label="About">
    <ul role="presentation">
        <li><a href="https://ocw.mit.edu/about/">About MIT OpenCourseWare</a></li>
        <li><a href="https://ocw.mit.edu/about/site-statistics/">Site Statistics</a></li>
        <li><a href="https://ocw.mit.edu/about/ocw-stories/">OCW Stories</a></li>
        <li><a href="https://ocw.mit.edu/about/newsletter/">Newsletter</a></li>
        <li><a href="https://chalk-radio.simplecast.com/">Chalk Radio Podcast</a></li>
        <li><a href="https://www.ocw-openmatters.org/">Open Matters Blog</a></li>
    </ul>
    </nav></div>
    </li>
</ul>
</nav></div></div>

</div>





<!--googleoff: index-->
<script>
  (function() {
	var cx = '012626166551961672889:owjdpuboktq';
	var gcse = document.createElement('script');
	gcse.type = 'text/javascript';
	gcse.async = true;
	gcse.src = 'https://cse.google.com/cse.js?cx=' + cx;
	var s = document.getElementsByTagName('script')[0];
	s.parentNode.insertBefore(gcse, s);
  })();
  window.onload = function(){
	document.getElementById('gsc-i-id1').placeholder = 'Search';	
  };

$(document).ready(function(){

$('.advanceSearch a').keydown(function(event){showSearchTips($(this),event);})
$('#searchTipsModal').keydown(function(event){showSearchTips($(this),event);})

function showSearchTips(obj,evt) {
// if pressed enter key
	if ( evt.which == 13 || evt.which == 32) {
		showModal();
		ga('send', 'pageview', "AdvanceSearch");
		$(".advanceSearch a").attr('aria-expanded', 'true');
		$('.searchTipsModal').focus();
		evt.preventDefault();
		}
	if ( evt.which == 27 ) {
		hideModal();
		$(".advanceSearch a").attr('aria-expanded', 'false');
		var modal = document.getElementById('searchTipsModal');
		modal.style.display = "none";
		$(".advanceSearch a").focus();
		evt.preventDefault();
		}
}

});
function showModal(){
	var modal = document.getElementById('searchTipsModal');
	modal.style.display = "block";
	ga('send', 'pageview', "AdvanceSearch");
	document.getElementById("searchTipsBtn").setAttribute("aria-expanded", true);
	window.setTimeout(function () {
    document.getElementById('searchTipsModal').focus(); }, 0);
}

function hideModal(){
	var modal = document.getElementById('searchTipsModal');
	modal.style.display = "none";
	document.getElementById("searchTipsBtn").setAttribute("aria-expanded", false);
}
</script>
<div id="search" role="search" class="grid_4 omega">
    	<table class="search">
				<tbody>
					<tr>
						<td><div class="searchboxheader"><searchbox-only resultsurl="/search/ocwsearch.htm"></searchbox-only></div></td>
						<td>
							<div class="advanceSearch">
								<a id="searchTipsBtn" onclick="showModal();" href="#" role="button" aria-label="search tips" aria-expanded="false" aria-describedby="searchtips">Search Tips</a>

								<!-- The Modal -->
								<div id="searchTipsModal" class="modal" tabindex="-1">
								  <!-- Modal content -->
									<div class="modal-content">
										<div class="modal-body">
											<button class="close" onclick="hideModal();" aria-label="close">X</button>
											<span>
												<b>Exclude words from your search</b>
												<br>Put - in front of a word you want to leave out. For example, jaguar speed -car
												<br><br>
												<b>Search for an exact match</b>
												<br>Put a word or phrase inside quotes. For example, "tallest building".
												<br><br>
												<b>Search for wildcards or unknown words</b>
												<br>Put a * in your word or phrase where you want to leave a placeholder. For example, "largest * in the world".
												<br><br>
												<b>Search within a range of numbers</b>
												<br>Put .. between two numbers. For example, camera $50..$100.
												<br><br>
												<b>Combine searches</b>
												<br>Put "OR" between each search query. For example,  marathon OR race.
												<br><br>
											</span>
										</div>
								  </div>
								</div>
							</div>
						</td>
					</tr>
				</tbody>
		</table>
</div>
<div class="clear"></div>
<!--googleon: index-->
<!-- *end header* -->

				
				
			</div>
<!-- top grid end -->
		</header><!-- top end -->
			
		<div id="center_media">
      	<div id="grid">
      		<div id="left">
        		<nav id="breadcrumb_media" aria-label="Breadcrumb">
                	<p>

    <a href="https://ocw.mit.edu/">Home</a>
    
        »
        
    
    
        
            <a href="https://ocw.mit.edu/courses">Courses</a>
            
                »
                
            
            
         
    
    
        
            <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science">Electrical Engineering and Computer Science</a>
            
                »
                
            
            
         
    
    
        
            <a href="../../../contents/index.htm">Mathematics for Computer Science</a>
            
                »
                
            
            
         
    
    
        
            <a href="../../../contents/video-lectures/index.htm">Video Lectures</a>
            
                »
                
            
            
         
    
    
        
            
            
            Lecture 11: Relations, Partial Orders, and Scheduling
         
    
</p>

            	</nav>
            	<div class="clear"></div>
        		<div id="media_title">
        		<h1 class="title" itemprop="name" property="dct:title">
        <span class="" id="parent-fieldname-title">
            Lecture 11: Relations, Partial Orders, and Scheduling
        </span>
    </h1>
        		</div>
           		<div class="clear"></div>
           		<div id="course_wrapper_media">
           			<nav id="course_nav" aria-label="Course">
           				<script language="javascript" type="text/javascript">
function toggleMenu(objID) {
  if (!document.getElementById) return;
  var ob = document.getElementById(objID);
  ob.className = (ob.className == 'selected')?'': 'selected';
}
function toggleClass(id)
{
  var divtoggleClass= document.getElementById(id);
  divtoggleClass.className = (divtoggleClass.className == 'mO')?'mC': 'mO';
  return false;
}
function changeAlt(id)
{
  id.alt = (id.alt == 'Expand Menu')?'Collapse Menu' : 'Expand Menu';
  id.title = (id.title == 'Expand Menu')?'Collapse Menu' : 'Expand Menu';
}
</script>
<!--Left Nav Starts -->


	<ul>			  
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/index.htm">
		                  Course Home  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/syllabus/index.htm">
		                  Syllabus  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/calendar/index.htm">
		                  Calendar  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/readings/index.htm">
		                  Readings  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="selected">
			   			<a href="../../../contents/video-lectures/index.htm">
		                  Video Lectures  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/recitations/index.htm">
		                  Recitations  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/assignments/index.htm">
		                  Assignments  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    <li class="">
			   			<a href="../../../contents/exams/index.htm">
		                  Exams  			                
	                    </a>
		        </li>
		    
         	
	
	
	    	
	    	    
		    
         	
	<!--second tal block close-->  
	
</ul>


<!--Left Nav Ends -->





           			</nav>
           			<main id="course_inner_media" aria-labelledby="media_title">
      					 
        <div class="" id="parent-fieldname-text">
            
            
        </div>
    
      					     
    
    



<script type="text/javascript">var caption_embed_1 ={'English - US': '/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-11-relations-partial-orders-and-scheduling/1nScXLQAQ9A.srt'}</script>     
     <div id="media-embed">
         <div class="attention_message" id="embed_1">
<p>Flash and JavaScript are required for this feature.</p>
<p>Download the video from <a href="http://itunes.apple.com/us/itunes-u/lecture-11-relations-partial/id503873536?i=110644975">iTunes U</a> or the <a href="http://www.archive.org/download/MIT6.042JF10/MIT6_042JF10_lec11_300k.mp4">Internet Archive</a>.</p>
</div>
     </div>
    
     <script type="text/javascript">ocw_embed_chapter_media('embed_1', 'https://www.youtube.com/v/1nScXLQAQ9A', 'youtube', '/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-11-relations-partial-orders-and-scheduling', 'https://img.youtube.com/vi/1nScXLQAQ9A/0.jpg',0,0, 'https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-11-relations-partial-orders-and-scheduling/1nScXLQAQ9A.srt')</script>
	 
	 
	 		
	 		<div id="transcript1"></div>
				 <script type="text/javascript">createThreePlayParams(2, 781482, "embed_1", 0, 0)</script>
			 
	

     <div id="media_resource_next_prev_nav" style="margin-top: 1em;">
        <p>
        
            <a href="../../../contents/video-lectures/lecture-10-graph-theory-iii/index.htm">
                <img src="../../../common/images/btn_previous_resource.png" style="margin: 0 30px 0 50px;" alt="Previous track" title="Previous track"></a>
     	
     	
        
            <a href="../../../contents/video-lectures/lecture-12-sums/index.htm"> 
                <img src="../../../common/images/btn_next_resource.png" alt="Next track" title="Next track"></a>
       
       </p>
     </div>
 


<script type="text/javascript">
		window.onload=function(){
		init();
		
		}
		var tabLinks = new Array();
		var contentDivs = new Array();
		function init() {
		  // Grab the tab links and content divs from the page
		  var tabListItems = document.getElementById('tabs').childNodes;
		  for ( var i = 0; i < tabListItems.length; i++ ) {
			if ( tabListItems[i].nodeName == "LI" ) {
			  var tabLink = getFirstChildWithTagName( tabListItems[i], 'A' );
			  var id = getHash( tabLink.getAttribute('href') );
			  tabLinks[id] = tabLink;
			  contentDivs[id] = document.getElementById( id );
			}
		  }
		  // Assign onclick events to the tab links, and
		  // highlight the first tab
		  var i = 0;
		  for ( var id in tabLinks ) {
			tabLinks[id].onclick = showTab;
			tabLinks[id].onfocus = function() { this.blur() };
			if ( i == 0 ) tabLinks[id].className = 'selected';
			i++;
		  }
		  // Hide all content divs except the first
		  var i = 0;
		  for ( var id in contentDivs ) {
			if ( i != 0 ) contentDivs[id].className = 'tabContent hide';
			i++;
		  }
		}
		function showTab() {
		  var selectedId = getHash( this.getAttribute('href') );
		  // Highlight the selected tab, and dim all others.
		  // Also show the selected content div, and hide all others.
		  for ( var id in contentDivs ) {
			if ( id == selectedId ) {
			  tabLinks[id].className = 'selected';
			  contentDivs[id].className = 'tabContent';
			} else {
			  tabLinks[id].className = '';
			  contentDivs[id].className = 'tabContent hide';
			}
		  }
		  // Stop the browser following the link
		  return false;
		}
		function getFirstChildWithTagName( element, tagName ) {
		  for ( var i = 0; i < element.childNodes.length; i++ ) {
			if ( element.childNodes[i].nodeName == tagName ) return element.childNodes[i];
		  }
		}
		function getHash( url ) {
		  var hashPos = url.lastIndexOf ( '#' );
		  return url.substring( hashPos + 1 );
		}
 </script>	
 

  <div id="media_tabs">
     
        <ul id="tabs">
            <li class="first">
                <a href="#vid_about" class="selected">About this Video</a>
            </li>
            <li class="">
                <a href="#vid_index" class="">Playlist</a>
            </li>
            <li class="">
                <a href="#vid_playlist" class="">Transcript</a>
            </li>
            <li class="">
                <a href="#vid_related" class="">Download this Video</a>
            </li>
        </ul>
   
        <div id="vid_about" itemprop="description" class="tabContent">
<p><strong>Description:</strong> Covers definitions and examples of basic relations, equivalence classes, Hasse diagrams and topological sorts, as well as other topics.</p> <p><strong>Speaker:</strong> Marten van Dijk</p> <p>The last 30 minutes of this video are not available.</p>
</div>
        <div id="vid_index" itemprop="description" class="tabContent hide">
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-1-introduction-and-proofs/index.htm">
<img src="https://img.youtube.com/vi/L3LMbpZIKhQ/default.jpg" title="Lecture 1: Introduction and Proofs" alt="Lecture 1: Introduction and Proofs">
<p>Lecture 1: Introduction and...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-2-induction/index.htm">
<img src="https://img.youtube.com/vi/z8HKWUWS-lA/default.jpg" title="Lecture 2: Induction" alt="Lecture 2: Induction">
<p>Lecture 2: Induction</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-3-strong-induction/index.htm">
<img src="https://img.youtube.com/vi/NuGDkmwEObM/default.jpg" title="Lecture 3: Strong Induction" alt="Lecture 3: Strong Induction">
<p>Lecture 3: Strong Induction</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-4-number-theory-i/index.htm">
<img src="https://img.youtube.com/vi/NuY7szYSXSw/default.jpg" title="Lecture 4: Number Theory I" alt="Lecture 4: Number Theory I">
<p>Lecture 4: Number Theory I</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-5-number-theory-ii/index.htm">
<img src="https://img.youtube.com/vi/XX7ePR21Ook/default.jpg" title="Lecture 5: Number Theory II" alt="Lecture 5: Number Theory II">
<p>Lecture 5: Number Theory II</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-6-graph-theory-and-coloring/index.htm">
<img src="https://img.youtube.com/vi/h9wxtqoa1jY/default.jpg" title="Lecture 6: Graph Theory and Coloring" alt="Lecture 6: Graph Theory and Coloring">
<p>Lecture 6: Graph Theory and...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-7-matching-problems/index.htm">
<img src="https://img.youtube.com/vi/5RSMLgy06Ew/default.jpg" title="Lecture 7: Matching Problems" alt="Lecture 7: Matching Problems">
<p>Lecture 7: Matching Problems</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-8-graph-theory-ii-minimum-spanning-trees/index.htm">
<img src="https://img.youtube.com/vi/GJpt_3ie4WU/default.jpg" title="Lecture 8: Graph Theory II: Minimum Spanning Trees" alt="Lecture 8: Graph Theory II: Minimum Spanning Trees">
<p>Lecture 8: Graph Theory II:...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-9-communication-networks/index.htm">
<img src="https://img.youtube.com/vi/bTyxpoi2dmM/default.jpg" title="Lecture 9: Communication Networks" alt="Lecture 9: Communication Networks">
<p>Lecture 9: Communication Ne...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-10-graph-theory-iii/index.htm">
<img src="https://img.youtube.com/vi/DOIp5D7VMS4/default.jpg" title="Lecture 10: Graph Theory III" alt="Lecture 10: Graph Theory III">
<p>Lecture 10: Graph Theory III</p></a>
</div>
<div class="related-media-thumbnail-nolink">
<div class="now-playing-resource">Now Playing</div>
<img src="https://img.youtube.com/vi/1nScXLQAQ9A/default.jpg" title="Lecture 11: Relations, Partial Orders, and Scheduling" alt="Lecture 11: Relations, Partial Orders, and Scheduling">
<p>Lecture 11: Relations, Part...</p>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-12-sums/index.htm">
<img src="https://img.youtube.com/vi/fAeShezAGLE/default.jpg" title="Lecture 12: Sums" alt="Lecture 12: Sums">
<p>Lecture 12: Sums</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-13-sums-and-asymptotics/index.htm">
<img src="https://img.youtube.com/vi/X9eErxRjQEI/default.jpg" title="Lecture 13: Sums and Asymptotics" alt="Lecture 13: Sums and Asymptotics">
<p>Lecture 13: Sums and Asympt...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-14-divide-and-conquer-recurrences/index.htm">
<img src="https://img.youtube.com/vi/Kqf0uO0oV6s/default.jpg" title="Lecture 14: Divide and Conquer Recurrences" alt="Lecture 14: Divide and Conquer Recurrences">
<p>Lecture 14: Divide and Conq...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-15-linear-recurrences/index.htm">
<img src="https://img.youtube.com/vi/TWBB-JlmYUc/default.jpg" title="Lecture 15: Linear Recurrences" alt="Lecture 15: Linear Recurrences">
<p>Lecture 15: Linear Recurrences</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-16-counting-rules-i/index.htm">
<img src="https://img.youtube.com/vi/pNt5Ll6hGqo/default.jpg" title="Lecture 16: Counting Rules I" alt="Lecture 16: Counting Rules I">
<p>Lecture 16: Counting Rules I</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-17-counting-rules-ii/index.htm">
<img src="https://img.youtube.com/vi/09yIb3VHhMI/default.jpg" title="Lecture 17: Counting Rules II" alt="Lecture 17: Counting Rules II">
<p>Lecture 17: Counting Rules II</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-18-probability-introduction/index.htm">
<img src="https://img.youtube.com/vi/SmFwFdESMHI/default.jpg" title="Lecture 18: Probability Introduction" alt="Lecture 18: Probability Introduction">
<p>Lecture 18: Probability Int...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-19-conditional-probability/index.htm">
<img src="https://img.youtube.com/vi/E6FbvM-FGZ8/default.jpg" title="Lecture 19: Conditional Probability" alt="Lecture 19: Conditional Probability">
<p>Lecture 19: Conditional Pro...</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-20-independence/index.htm">
<img src="https://img.youtube.com/vi/l1BCv3qqW4A/default.jpg" title="Lecture 20: Independence" alt="Lecture 20: Independence">
<p>Lecture 20: Independence</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-21-random-variables/index.htm">
<img src="https://img.youtube.com/vi/MOfhhFaQdjw/default.jpg" title="Lecture 21: Random Variables" alt="Lecture 21: Random Variables">
<p>Lecture 21: Random Variables</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-22-expectation-i/index.htm">
<img src="https://img.youtube.com/vi/gGlMSe7uEkA/default.jpg" title="Lecture 22: Expectation I" alt="Lecture 22: Expectation I">
<p>Lecture 22: Expectation I</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-23-expectation-ii/index.htm">
<img src="https://img.youtube.com/vi/oI9fMUqgfxY/default.jpg" title="Lecture 23: Expectation II" alt="Lecture 23: Expectation II">
<p>Lecture 23: Expectation II</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-24-large-deviations/index.htm">
<img src="https://img.youtube.com/vi/q4mwO2qS2z4/default.jpg" title="Lecture 24: Large Deviations" alt="Lecture 24: Large Deviations">
<p>Lecture 24: Large Deviations</p></a>
</div>
<div class="related-media-thumbnail">
<a href="../../../contents/video-lectures/lecture-25-random-walks/index.htm">
<img src="https://img.youtube.com/vi/56iFMY8QW2k/default.jpg" title="Lecture 25: Random Walks" alt="Lecture 25: Random Walks">
<p>Lecture 25: Random Walks</p></a>
</div>
</div>
        <div id="vid_playlist" itemprop="description" class="tabContent hide">
<ul><li><a class="transcript-link" title="Open in a new window." alt="Open in a new window." style="text-decoration: none; font-size: 1.0em;" target="_blank" text-decoration: none font-size: href="../../../contents/video-lectures/lecture-11-relations-partial-orders-and-scheduling/1nScXLQAQ9A.pdf"> Download English-US transcript (PDF)</a></li></ul>
<p><span m="410">The</span> <span m="510">following</span> <span m="950">content</span> <span m="1550">is</span> <span m="1660">provided</span> <span m="2110">under</span> <span m="2390">a</span> <span m="2420">Creative</span> <span m="2830">Commons</span> <span m="3230">license.</span> <span m="4340">Your</span> <span m="4530">support</span> <span m="5040">will</span> <span m="5200">help</span> <span m="5440">MIT</span> <span m="5890">OpenCourseWare</span> <span m="6680">continue</span> <span m="7190">to</span> <span m="7270">offer</span> <span m="7690">high</span> <span m="7930">quality</span> <span m="8440">educational</span> <span m="9070">resources</span> <span m="9700">for</span> <span m="9850">free.</span> <span m="11050">To</span> <span m="11060">make</span> <span m="11260">a</span> <span m="11310">donation</span> <span m="11990">or</span> <span m="12260">view</span> <span m="12700">additional</span> <span m="13120">materials</span> <span m="13660">from</span> <span m="13810">hundreds</span> <span m="14250">of</span> <span m="14360">MIT</span> <span m="14780">courses,</span> <span m="15880">visit</span> <span m="16110">MIT</span> <span m="16530">OpenCourseWare</span> <span m="17580">at</span> <span m="17750">ocw.mit.edu.</span> </p>
<p><span m="23480">MARTEN VAN DIJK:</span> <span m="23920">So</span> <span m="24220">today</span> <span m="24510">we're</span> <span m="24640">going</span> <span m="24860">to</span> <span m="24960">talk</span> <span m="25230">about</span> <span m="26850">relations.</span> <span m="29670">We're</span> <span m="29790">going</span> <span m="30020">to</span> <span m="30120">talk</span> <span m="30350">about</span> <span m="30550">partial</span> <span m="30970">orders.</span> <span m="32380">Wow</span> <span m="32500">this</span> <span m="32735">is</span> <span m="32970">loud.</span> <span m="33862">Could</span> <span m="34310">you</span> <span m="34370">put</span> <span m="34430">it</span> <span m="34590">a</span> <span m="34710">bit</span> <span m="34830">softer?</span> <span m="38130">So</span> <span m="38760">we're</span> <span m="38830">going</span> <span m="39120">to</span> <span m="39570">talk</span> <span m="39690">about</span> <span m="39810">relations,</span> <span m="40870">partial</span> <span m="41330">orders,</span> <span m="42060">and</span> <span m="42210">then</span> <span m="42360">parallel</span> <span m="42840">task</span> <span m="44130">scheduling.</span> <span m="45590">So</span> <span m="46290">well,</span> <span m="46550">we'll</span> <span m="46890">start</span> <span m="47140">out</span> <span m="47300">with</span> <span m="47510">a</span> <span m="47565">few</span> <span m="47620">definitions</span> <span m="48550">as</span> <span m="48700">usual</span> <span m="50450">and</span> <span m="52810">examples</span> <span m="53300">will</span> <span m="53500">explain</span> <span m="53930">what</span> <span m="54070">you're</span> <span m="54200">talking</span> <span m="54580">about</span> <span m="54850">here.</span> </p>
<p><span m="55760">So</span> <span m="56380">what</span> <span m="56520">about</span> <span m="56750">relations?</span> <span m="58320">Well,</span> <span m="58340">relations</span> <span m="58940">are</span> <span m="59630">very</span> <span m="59870">simple</span> <span m="62140">definition.</span> <span m="63300">A</span> <span m="63590">relation</span> <span m="69190">from</span> <span m="69460">a</span> <span m="69520">set</span> <span m="70100">A</span> <span m="71360">to</span> <span m="71750">a</span> <span m="71850">set</span> <span m="72230">B</span> <span m="75880">is</span> <span m="76240">really</span> <span m="78410">a</span> <span m="78660">subset</span> <span m="79760">of</span> <span m="79990">the</span> <span m="80080">cross</span> <span m="80430">product</span> <span m="80800">of</span> <span m="80940">the</span> <span m="81040">two.</span> <span m="83610">So</span> <span m="83780">let</span> <span m="83870">me</span> <span m="83960">give</span> <span m="84150">an</span> <span m="84220">example.</span> <span m="86270">It's</span> <span m="86420">a</span> <span m="86480">subset</span> <span m="86980">R</span> <span m="87295">that</span> <span m="90660">has</span> <span m="90860">its</span> <span m="91100">elements</span> <span m="91560">in</span> <span m="91650">a</span> <span m="91710">cross</span> <span m="92000">product</span> <span m="92330">of</span> <span m="92410">A</span> <span m="92490">and</span> <span m="92840">B,</span> <span m="93020">which</span> <span m="93210">really</span> <span m="93430">means</span> <span m="94320">that</span> <span m="94470">it</span> <span m="94580">has</span> <span m="94920">pairs</span> <span m="95290">where</span> <span m="95720">the</span> <span m="95770">first</span> <span m="96180">element</span> <span m="96610">is</span> <span m="96750">drawn</span> <span m="97100">from</span> <span m="97550">A</span> <span m="98010">and</span> <span m="98050">the</span> <span m="98090">second</span> <span m="98450">element</span> <span m="98910">is</span> <span m="99030">from</span> <span m="99280">B.</span> </p>
<p><span m="100976">So</span> <span m="101400">for</span> <span m="101530">example,</span> <span m="103460">if</span> <span m="103630">you're</span> <span m="103740">thinking</span> <span m="104140">about</span> <span m="105180">the</span> <span m="105420">classes</span> <span m="105700">that</span> <span m="105980">you're</span> <span m="106160">taking</span> <span m="107320">as</span> <span m="107730">say,</span> <span m="108460">set</span> <span m="108810">B</span> <span m="109540">and</span> <span m="109760">all</span> <span m="109900">the</span> <span m="109980">students</span> <span m="110650">set</span> <span m="110950">A,</span> <span m="111640">well,</span> <span m="111790">then</span> <span m="111885">you</span> <span m="111980">can</span> <span m="112980">describe</span> <span m="114140">this</span> <span m="114360">is</span> <span m="114530">as</span> <span m="114555">a</span> <span m="114580">relationship</span> <span m="116130">where</span> <span m="117050">we</span> <span m="117190">have</span> <span m="117440">tuples</span> <span m="118160">a,</span> <span m="118380">b</span> <span m="119670">where</span> <span m="120160">a</span> <span m="120210">student</span> <span m="120690">a</span> <span m="124190">is</span> <span m="124480">taking</span> <span m="124930">class</span> <span m="125470">b.</span> <span m="128080">So</span> <span m="131660">a</span> <span m="131750">relation</span> <span m="132210">is</span> <span m="132370">really</span> <span m="132630">just</span> <span m="133650">a</span> <span m="133750">set</span> <span m="134210">of</span> <span m="134370">pairs.</span> <span m="135540">The</span> <span m="135610">first</span> <span m="136010">part</span> <span m="136430">of</span> <span m="136830">the</span> <span m="137130">pair</span> <span m="137360">is</span> <span m="137640">in</span> <span m="137710">set</span> <span m="137797">A,</span> <span m="137885">the</span> <span m="137972">second</span> <span m="138060">one</span> <span m="138410">in</span> <span m="138620">B.</span> </p>
<p><span m="141440">Now,</span> <span m="141610">we</span> <span m="141730">will</span> <span m="142310">use</span> <span m="142660">different</span> <span m="142950">notation</span> <span m="143630">for</span> <span m="144210">indicating</span> <span m="145550">that</span> <span m="146450">a</span> <span m="146725">pair</span> <span m="147650">is</span> <span m="148110">in</span> <span m="148320">this</span> <span m="148590">subset,</span> <span m="149740">so</span> <span m="150080">we'll</span> <span m="150410">be</span> <span m="150570">talking</span> <span m="150890">about</span> <span m="151280">further</span> <span m="151890">properties,</span> <span m="152340">then</span> <span m="152670">it</span> <span m="152730">will</span> <span m="152790">become</span> <span m="153100">more</span> <span m="153290">clear,</span> <span m="153740">but</span> <span m="153820">we</span> <span m="153990">will</span> <span m="154120">also</span> <span m="154510">write</span> <span m="155460">that</span> <span m="156370">a</span> <span m="156710">is</span> <span m="156970">to</span> <span m="157100">relate</span> <span m="157530">this</span> <span m="157740">to</span> <span m="157910">b.</span> <span m="158550">So</span> <span m="158670">instead</span> <span m="159080">of</span> <span m="160100">the</span> <span m="160230">pair</span> <span m="160570">a,</span> <span m="160820">b</span> <span m="161070">is</span> <span m="161270">an</span> <span m="161450">element</span> <span m="162240">of</span> <span m="162530">R,</span> <span m="163530">you</span> <span m="163630">may</span> <span m="163790">write</span> <span m="164190">a</span> <span m="164450">R</span> <span m="164946">b,</span> <span m="166600">or</span> <span m="166940">we</span> <span m="167050">say</span> <span m="167470">a</span> <span m="167875">and</span> <span m="168280">then</span> <span m="168390">we</span> <span m="168490">use</span> <span m="169050">this</span> <span m="169610">symbol</span> <span m="170410">with</span> <span m="170570">a</span> <span m="170630">subscript</span> <span m="171300">R</span> <span m="173230">b.</span> </p>
<p><span m="174830">So</span> <span m="175380">we</span> <span m="175510">use</span> <span m="176010">the</span> <span m="178450">relational</span> <span m="178930">symbol</span> <span m="179690">in</span> <span m="179850">between</span> <span m="180490">a</span> <span m="180810">and</span> <span m="181250">b</span> <span m="182270">in</span> <span m="182440">these</span> <span m="182650">two</span> <span m="182780">cases.</span> <span m="183740">And</span> <span m="183900">the</span> <span m="184200">reason</span> <span m="184380">for</span> <span m="184445">that</span> <span m="184510">becomes</span> <span m="184870">clear</span> <span m="185150">if</span> <span m="185260">you</span> <span m="185660">start</span> <span m="185990">talking</span> <span m="186370">about</span> <span m="186640">the</span> <span m="186720">properties,</span> <span m="187240">but</span> <span m="187370">let</span> <span m="187510">me</span> <span m="187600">first</span> <span m="187900">give</span> <span m="187920">a</span> <span m="187940">few</span> <span m="188230">more</span> <span m="188420">examples</span> <span m="190080">and</span> <span m="191670">talk</span> <span m="191960">about</span> <span m="192440">the</span> <span m="192570">types</span> <span m="192870">of</span> <span m="194540">relations</span> <span m="195230">that</span> <span m="195350">you're</span> <span m="195490">really</span> <span m="195740">interested</span> <span m="196280">in.</span> <span m="196390">We</span> <span m="197150">really</span> <span m="197570">are</span> <span m="197770">interested</span> <span m="198490">in</span> <span m="199640">a</span> <span m="199690">relation</span> <span m="200580">on</span> <span m="201620">a</span> <span m="201730">set</span> <span m="202095">A,</span> <span m="203370">and</span> <span m="203510">this</span> <span m="203660">is</span> <span m="203820">really</span> <span m="206350">a</span> <span m="206460">subset</span> <span m="209120">R</span> <span m="210990">that</span> <span m="211250">is</span> <span m="211280">a</span> <span m="211310">cross</span> <span m="211740">product</span> <span m="212180">of</span> <span m="212360">A</span> <span m="212560">with</span> <span m="212750">itself.</span> <span m="213550">So</span> <span m="213720">essentially,</span> <span m="215030">A</span> <span m="215140">is</span> <span m="215250">equal</span> <span m="215610">to</span> <span m="215750">B</span> <span m="216120">in</span> <span m="216450">the</span> <span m="216550">definition</span> <span m="217130">right</span> <span m="217360">up</span> <span m="217500">here.</span> </p>
<p><span m="219420">Now,</span> <span m="219660">examples</span> <span m="219935">that</span> <span m="220210">we</span> <span m="220450">have</span> <span m="220630">for</span> <span m="220670">this</span> <span m="220980">one</span> <span m="221680">is,</span> <span m="222110">for</span> <span m="222280">example,</span> <span m="223150">we</span> <span m="223230">may</span> <span m="223560">have</span> <span m="224070">A</span> <span m="224570">to</span> <span m="224680">B,</span> <span m="225480">all</span> <span m="225780">in</span> <span m="225990">the</span> <span m="226110">integers,</span> <span m="226770">positive</span> <span m="227240">and</span> <span m="227430">negative,</span> <span m="228420">and</span> <span m="228670">then</span> <span m="229730">we</span> <span m="229950">can</span> <span m="230720">say,</span> <span m="231050">for</span> <span m="231220">example,</span> <span m="231790">x</span> <span m="232400">is</span> <span m="232670">related</span> <span m="233060">to</span> <span m="233250">y</span> <span m="233900">if</span> <span m="234090">and</span> <span m="234230">only</span> <span m="234600">if</span> <span m="236120">x</span> <span m="236520">is,</span> <span m="236810">for</span> <span m="236980">example,</span> <span m="238550">congruent</span> <span m="239060">to</span> <span m="239400">y</span> <span m="240460">modulo</span> <span m="240940">5.</span> <span m="242560">This</span> <span m="242670">would</span> <span m="242790">be</span> <span m="243040">a</span> <span m="243100">proper</span> <span m="243610">relation.</span> <span m="246036">We</span> <span m="246460">have</span> <span m="246670">not</span> <span m="246800">yet</span> <span m="246970">talked</span> <span m="247180">about</span> <span m="247510">special</span> <span m="247870">properties.</span> <span m="248620">We</span> <span m="248700">will</span> <span m="248820">come</span> <span m="249000">to</span> <span m="249120">that.</span> <span m="250320">Other</span> <span m="250530">examples</span> <span m="251140">are,</span> <span m="251700">well,</span> <span m="251840">we</span> <span m="251970">could</span> <span m="252200">take</span> <span m="254410">all</span> <span m="254710">the</span> <span m="257200">positive</span> <span m="257649">integers,</span> <span m="258050">0,</span> <span m="258839">1,</span> <span m="259180">and</span> <span m="259370">so</span> <span m="259709">on</span> <span m="260029">and</span> <span m="260190">so</span> <span m="260300">forth,</span> <span m="261490">and</span> <span m="261760">then</span> <span m="261970">right</span> <span m="262280">so</span> <span m="262670">x</span> <span m="263130">is</span> <span m="263290">related</span> <span m="263630">to</span> <span m="263790">y</span> <span m="264230">if</span> <span m="264410">and</span> <span m="264540">only</span> <span m="264860">if,</span> <span m="265560">for</span> <span m="265710">example,</span> <span m="266050">you</span> <span m="266140">could</span> <span m="266300">say</span> <span m="266520">that</span> <span m="266770">x</span> <span m="267500">defines</span> <span m="268240">y.</span> <span m="269070">That's</span> <span m="269260">another</span> <span m="269520">relationship</span> <span m="270240">that</span> <span m="270320">we</span> <span m="270400">could</span> <span m="270690">use.</span> </p>
<p><span m="271660">Notice,</span> <span m="271930">by</span> <span m="272080">the</span> <span m="272190">way</span> <span m="273180">that</span> <span m="274870">in</span> <span m="275330">the</span> <span m="275410">correct</span> <span m="275750">[INAUDIBLE]</span> <span m="276250">that</span> <span m="276610">I</span> <span m="276690">put</span> <span m="276770">here,</span> <span m="277410">I</span> <span m="277520">already</span> <span m="277830">used</span> <span m="278200">sort</span> <span m="278420">of</span> <span m="278550">relational</span> <span m="279030">symbols</span> <span m="279530">right</span> <span m="279840">in</span> <span m="279960">the</span> <span m="280030">middle</span> <span m="280380">between</span> <span m="280850">x</span> <span m="281100">and</span> <span m="281240">y</span> <span m="281930">over</span> <span m="282220">here.</span> <span m="282990">So</span> <span m="283170">that's</span> <span m="283740">already</span> <span m="284050">indicating</span> <span m="284760">why</span> <span m="285860">we</span> <span m="286020">are</span> <span m="286260">using</span> <span m="286630">a</span> <span m="286710">notation</span> <span m="287610">that</span> <span m="287930">I</span> <span m="288030">put</span> <span m="288260">up</span> <span m="288430">here.</span> <span m="289670">So</span> <span m="290210">another</span> <span m="290540">example</span> <span m="291120">is,</span> <span m="291870">for</span> <span m="292070">example,</span> <span m="293100">we</span> <span m="293140">have</span> <span m="294850">that</span> <span m="295080">x</span> <span m="295550">is</span> <span m="295740">related</span> <span m="296130">to</span> <span m="296260">y</span> <span m="297130">if</span> <span m="297360">and</span> <span m="297460">only</span> <span m="297800">if</span> <span m="299150">x</span> <span m="299620">is</span> <span m="301580">at</span> <span m="301750">most</span> <span m="302070">y.</span> <span m="303570">This</span> <span m="303730">is</span> <span m="303820">also</span> <span m="303995">a</span> <span m="304170">relation.</span> </p>
<p><span m="306060">So</span> <span m="306250">now</span> <span m="306400">what</span> <span m="306620">are</span> <span m="306760">the</span> <span m="306810">special</span> <span m="307180">property</span> <span m="307540">that</span> <span m="307710">we</span> <span m="307780">are</span> <span m="308010">interested</span> <span m="308600">in</span> <span m="308950">and</span> <span m="310321">those</span> <span m="310780">that</span> <span m="310845">will</span> <span m="310910">make</span> <span m="311150">relations</span> <span m="311570">special</span> <span m="312350">and</span> <span m="312490">then</span> <span m="312600">we</span> <span m="312740">can</span> <span m="312900">talk</span> <span m="313200">about--</span> <span m="315642">actually,</span> <span m="316100">I</span> <span m="316210">forgot</span> <span m="318140">one</span> <span m="318870">item</span> <span m="319850">that</span> <span m="319950">we</span> <span m="320060">will</span> <span m="320250">talk</span> <span m="320520">about</span> <span m="320800">as</span> <span m="320940">well,</span> <span m="322280">which</span> <span m="322420">are</span> <span m="322660">equivalents</span> <span m="323600">classes,</span> <span m="325620">equivalence</span> <span m="329960">relations.</span> <span m="332050">So</span> <span m="332270">we</span> <span m="332380">will</span> <span m="332530">see</span> <span m="333170">when</span> <span m="333290">we</span> <span m="333460">talk</span> <span m="333700">about</span> <span m="333865">the</span> <span m="334030">properties</span> <span m="334500">right</span> <span m="334760">now</span> <span m="335460">that</span> <span m="335650">we</span> <span m="336340">will</span> <span m="336490">be</span> <span m="337060">defining</span> <span m="337820">very</span> <span m="338070">special</span> <span m="338660">types</span> <span m="338970">of</span> <span m="339100">relations</span> <span m="339860">and</span> <span m="340020">we</span> <span m="340110">will</span> <span m="340200">talk</span> <span m="340430">about</span> <span m="340690">these</span> <span m="340960">two,</span> <span m="341470">equivalents</span> <span m="342060">relations</span> <span m="342680">and</span> <span m="342860">partial</span> <span m="343250">orders.</span> </p>
<p><span m="345990">So</span> <span m="346150">what</span> <span m="346300">are</span> <span m="346390">the</span> <span m="346510">properties?</span> <span m="351600">Actually</span> <span m="351930">before</span> <span m="352310">we</span> <span m="352410">go</span> <span m="352610">into</span> <span m="352830">those</span> <span m="353040">properties,</span> <span m="354180">let</span> <span m="354330">us</span> <span m="354480">just</span> <span m="354650">first</span> <span m="354900">describe</span> <span m="356140">what</span> <span m="356430">the</span> <span m="356500">relationship,</span> <span m="357180">how</span> <span m="357560">we</span> <span m="357670">can</span> <span m="357800">describe</span> <span m="358210">it</span> <span m="359050">in</span> <span m="359330">a</span> <span m="359820">different</span> <span m="360330">way.</span> <span m="361160">Actually</span> <span m="361600">relation</span> <span m="361885">is</span> <span m="362170">nothing</span> <span m="362460">more</span> <span m="363220">than</span> <span m="363470">a</span> <span m="363510">directed</span> <span m="363960">graph,</span> <span m="365190">like</span> <span m="366520">R</span> <span m="367700">over</span> <span m="367970">here</span> <span m="368220">is</span> <span m="368440">a</span> <span m="368500">subset</span> <span m="369640">of</span> <span m="370810">a</span> <span m="370990">cross</span> <span m="371390">product</span> <span m="371670">with</span> <span m="371810">a.</span> <span m="371940">So</span> <span m="372420">that's</span> <span m="372760">pairs</span> <span m="372850">and</span> <span m="372940">you</span> <span m="373130">can</span> <span m="373280">think</span> <span m="373560">of</span> <span m="373660">those</span> <span m="374000">as</span> <span m="374160">being</span> <span m="374480">edges.</span> <span m="376080">So</span> <span m="376230">let</span> <span m="376380">us</span> <span m="376570">write</span> <span m="376730">it</span> <span m="376850">down</span> <span m="377100">as</span> <span m="377240">well.</span> </p>
<p><span m="378220">So</span> <span m="378490">set</span> <span m="378910">A</span> <span m="380580">together</span> <span m="383570">with</span> <span m="386110">R</span> <span m="389340">is</span> <span m="390390">a</span> <span m="391320">directed</span> <span m="391790">graph.</span> <span m="395600">And</span> <span m="396520">the</span> <span m="396650">idea</span> <span m="396950">is</span> <span m="397150">very</span> <span m="397350">simple.</span> <span m="399456">The</span> <span m="399860">directed</span> <span m="400350">graph</span> <span m="400750">has</span> <span m="401110">vertices</span> <span m="403210">V</span> <span m="403530">and</span> <span m="403860">edge</span> <span m="404080">set</span> <span m="404300">E</span> <span m="406120">where</span> <span m="407270">we</span> <span m="407490">take</span> <span m="407990">V</span> <span m="408390">to</span> <span m="408490">be</span> <span m="408720">equal</span> <span m="409080">to</span> <span m="409400">A</span> <span m="410675">and</span> <span m="411100">the</span> <span m="411240">edge</span> <span m="411500">set</span> <span m="411760">equal</span> <span m="412020">to</span> <span m="412160">R.</span> <span m="414640">So</span> <span m="414860">for</span> <span m="415040">example,</span> <span m="416190">we</span> <span m="416200">could</span> <span m="417480">create</span> <span m="417860">a</span> <span m="417950">small</span> <span m="418320">little</span> <span m="418800">graph,</span> <span m="420650">for</span> <span m="420820">example,</span> <span m="421260">for</span> <span m="421280">three</span> <span m="421940">persons,</span> <span m="423280">Julie</span> <span m="424140">and</span> <span m="424820">Bill</span> <span m="426380">and</span> <span m="426890">another</span> <span m="427170">one,</span> <span m="427380">Rob.</span> <span m="428970">And</span> <span m="429220">suppose</span> <span m="429660">that</span> <span m="429760">the</span> <span m="429840">directed</span> <span m="430180">edges</span> <span m="430700">indicate</span> <span m="431450">whether</span> <span m="432330">one</span> <span m="432570">person</span> <span m="432950">likes</span> <span m="433270">the</span> <span m="433380">other.</span> </p>
<p><span m="433820">So</span> <span m="434000">for</span> <span m="434150">example</span> <span m="435140">Julie</span> <span m="436270">likes</span> <span m="436630">Bill</span> <span m="437890">and</span> <span m="438070">Bill</span> <span m="438280">likes</span> <span m="438510">himself,</span> <span m="439620">but</span> <span m="439750">likes</span> <span m="440020">no</span> <span m="440180">one</span> <span m="440370">else.</span> <span m="443690">Julie</span> <span m="443980">also</span> <span m="444260">likes</span> <span m="444630">Rob,</span> <span m="444990">but</span> <span m="445130">does</span> <span m="445300">not</span> <span m="445410">like</span> <span m="445640">herself</span> <span m="446670">and</span> <span m="446830">Rob</span> <span m="447030">really</span> <span m="447280">likes</span> <span m="447480">Julie,</span> <span m="447660">but</span> <span m="448470">does</span> <span m="448660">not</span> <span m="448770">like</span> <span m="449010">himself.</span> <span m="449510">So</span> <span m="449630">for</span> <span m="449790">example,</span> <span m="454340">you</span> <span m="454480">could</span> <span m="454630">create</span> <span m="454920">a</span> <span m="454970">graph</span> <span m="455530">where</span> <span m="456070">all</span> <span m="456210">the</span> <span m="456320">directed</span> <span m="456730">edge</span> <span m="457140">really</span> <span m="457520">represent</span> <span m="462230">the</span> <span m="462420">relations</span> <span m="462980">that</span> <span m="463120">you</span> <span m="463200">have</span> <span m="463410">described</span> <span m="463900">by</span> <span m="464110">R.</span> </p>
<p><span m="465260">So</span> <span m="466722">we</span> <span m="467120">will</span> <span m="467340">use</span> <span m="467610">this</span> <span m="468080">later</span> <span m="468380">on</span> <span m="469220">and</span> <span m="470550">the</span> <span m="470630">special</span> <span m="471060">properties</span> <span m="471207">that</span> <span m="471355">we</span> <span m="471650">are</span> <span m="471730">interested</span> <span m="472230">in</span> <span m="474800">are</span> <span m="474980">the</span> <span m="475040">following.</span> <span m="476030">So</span> <span m="476140">the</span> <span m="476250">properties</span> <span m="476880">are</span> <span m="478920">that</span> <span m="479550">relations</span> <span m="480280">can</span> <span m="481510">be</span> <span m="482000">reflexive.</span> <span m="483620">So</span> <span m="483930">a</span> <span m="484240">relation</span> <span m="488200">R</span> <span m="488990">on</span> <span m="490258">A</span> <span m="491620">is</span> <span m="493530">reflexive</span> <span m="496970">if</span> <span m="499670">x</span> <span m="500070">is</span> <span m="500270">related</span> <span m="500710">to</span> <span m="500840">itself</span> <span m="501770">for</span> <span m="502370">all</span> <span m="502660">x,</span> <span m="504570">so</span> <span m="509300">for</span> <span m="509600">all</span> <span m="509860">x</span> <span m="510280">in</span> <span m="510650">A.</span> <span m="514659">Well,</span> <span m="514900">for</span> <span m="515039">example,</span> <span m="515690">in</span> <span m="515799">this</span> <span m="515990">particular</span> <span m="516429">graph,</span> <span m="517440">that</span> <span m="517540">is</span> <span m="517640">not</span> <span m="517730">the</span> <span m="517830">case.</span> <span m="519120">If</span> <span m="519789">Julie</span> <span m="520230">and</span> <span m="520370">Rob</span> <span m="520630">would</span> <span m="520780">also</span> <span m="521090">like</span> <span m="521340">themselves,</span> <span m="522200">then</span> <span m="522440">the</span> <span m="522530">relationship</span> <span m="523159">up</span> <span m="523320">here</span> <span m="524169">would</span> <span m="524250">actually</span> <span m="524520">be</span> <span m="524670">reflexive.</span> </p>
<p><span m="527220">We</span> <span m="527340">have</span> <span m="528750">symmetry,</span> <span m="530380">so</span> <span m="530590">we</span> <span m="530700">call</span> <span m="530920">a</span> <span m="530980">relationship</span> <span m="532110">symmetric</span> <span m="535410">if</span> <span m="535740">x</span> <span m="537420">likes</span> <span m="538070">y,</span> <span m="539870">then</span> <span m="540110">that</span> <span m="540200">should</span> <span m="540500">imply</span> <span m="541070">that</span> <span m="541250">y</span> <span m="541670">also</span> <span m="542140">likes</span> <span m="542720">x</span> <span m="545040">and</span> <span m="545200">it</span> <span m="545270">should,</span> <span m="545490">of</span> <span m="545610">course,</span> <span m="545970">hold</span> <span m="546220">for</span> <span m="546460">all</span> <span m="546860">x</span> <span m="547140">and</span> <span m="547310">y.</span> <span m="554040">We</span> <span m="554220">have</span> <span m="554880">a</span> <span m="555160">property</span> <span m="555620">that</span> <span m="555915">we</span> <span m="556062">call</span> <span m="556210">antisymmetric,</span> <span m="560760">which</span> <span m="560920">is</span> <span m="561110">the</span> <span m="561230">opposite</span> <span m="561630">of</span> <span m="561740">this.</span> <span m="562270">Antisymmetric</span> <span m="563130">means</span> <span m="564120">that</span> <span m="567650">if</span> <span m="569550">x</span> <span m="570210">likes</span> <span m="570630">y</span> <span m="572290">and</span> <span m="572940">y</span> <span m="573360">likes</span> <span m="574920">x,</span> <span m="575820">then</span> <span m="576300">x</span> <span m="576540">and</span> <span m="576650">y</span> <span m="576780">must</span> <span m="576990">be</span> <span m="577100">the</span> <span m="577190">same.</span> <span m="578990">So</span> <span m="579070">this</span> <span m="579240">really</span> <span m="579480">means</span> <span m="579870">that</span> <span m="580610">it's</span> <span m="581430">not</span> <span m="581640">really</span> <span m="581900">possible</span> <span m="582750">to</span> <span m="583030">like</span> <span m="583480">someone</span> <span m="583930">else</span> <span m="585240">and</span> <span m="585810">that</span> <span m="585990">someone</span> <span m="586330">else</span> <span m="586620">also</span> <span m="587050">likes</span> <span m="588430">x,</span> <span m="589620">because</span> <span m="590920">according</span> <span m="591310">to</span> <span m="591430">the</span> <span m="591650">antisymmetrical</span> <span m="592960">property,</span> <span m="593870">that</span> <span m="594040">would</span> <span m="594210">then</span> <span m="594320">imply</span> <span m="594615">that</span> <span m="594910">x</span> <span m="595180">is</span> <span m="595340">actually</span> <span m="595700">equal</span> <span m="595890">to</span> <span m="596030">y.</span> <span m="597080">So</span> <span m="597950">these</span> <span m="598300">two</span> <span m="598560">definitions</span> <span m="599190">are</span> <span m="600080">opposite</span> <span m="600460">from</span> <span m="600620">one</span> <span m="600790">another.</span> </p>
<p><span m="601950">And</span> <span m="602350">the</span> <span m="602440">final</span> <span m="602830">one</span> <span m="603020">that</span> <span m="603170">we're</span> <span m="603300">interested</span> <span m="603840">in</span> <span m="604430">is</span> <span m="604640">transitivity.</span> <span m="613400">So</span> <span m="613620">the</span> <span m="613660">relationship</span> <span m="614130">is</span> <span m="614270">transitive</span> <span m="615840">if</span> <span m="618380">x</span> <span m="621670">likes</span> <span m="622060">y</span> <span m="623050">and</span> <span m="624080">y</span> <span m="624880">likes</span> <span m="625490">z,</span> <span m="627712">then</span> <span m="628640">x</span> <span m="629350">also</span> <span m="629750">likes</span> <span m="630140">z.</span> <span m="633110">So</span> <span m="633310">let's</span> <span m="633500">have</span> <span m="633680">a</span> <span m="633740">look</span> <span m="633980">at</span> <span m="634620">these</span> <span m="634850">few</span> <span m="635250">examples</span> <span m="635970">and</span> <span m="636180">see</span> <span m="636870">whether</span> <span m="637100">we</span> <span m="637260">can</span> <span m="637460">figure</span> <span m="637830">out</span> <span m="640130">what</span> <span m="640320">kind</span> <span m="640470">of</span> <span m="640540">properties</span> <span m="641020">they</span> <span m="641180">have.</span> </p>
<p><span m="642890">So</span> <span m="643580">let's</span> <span m="643750">make</span> <span m="643940">a</span> <span m="644000">table</span> <span m="647080">and</span> <span m="649420">let's</span> <span m="649700">first</span> <span m="649990">consider</span> <span m="650490">that</span> <span m="650730">x</span> <span m="651320">is</span> <span m="651500">congruent</span> <span m="651930">to</span> <span m="652060">y</span> <span m="652310">modulo</span> <span m="652780">5</span> <span m="655740">and</span> <span m="656900">next</span> <span m="659270">divisibility</span> <span m="660210">and</span> <span m="660330">the</span> <span m="660410">other</span> <span m="660590">one</span> <span m="660830">is</span> <span m="661860">less</span> <span m="662080">than</span> <span m="662250">or</span> <span m="662370">equal</span> <span m="662650">to.</span> <span m="663830">So</span> <span m="665190">are</span> <span m="665420">they</span> <span m="665590">reflexive</span> <span m="666740">is</span> <span m="666960">the</span> <span m="667230">first</span> <span m="667620">question</span> <span m="669100">and</span> <span m="669220">they</span> <span m="669320">we</span> <span m="669430">want</span> <span m="669580">to</span> <span m="669690">know</span> <span m="669860">whether</span> <span m="669980">they're</span> <span m="670280">symmetric</span> <span m="672490">and</span> <span m="673040">antisymmetric</span> <span m="677410">and</span> <span m="677890">transitive.</span> <span m="683080">So</span> <span m="684120">what</span> <span m="684240">about</span> <span m="684480">this</span> <span m="684670">one</span> <span m="684820">over</span> <span m="685050">here?</span> <span m="686810">So</span> <span m="687980">can</span> <span m="688120">you</span> <span m="688210">help</span> <span m="688440">me</span> <span m="688690">figure</span> <span m="689100">out</span> <span m="689320">whether</span> <span m="689545">they're</span> <span m="689770">reflexive</span> <span m="690540">and</span> <span m="690710">symmetric</span> <span m="691240">or</span> <span m="691370">antisymmetric</span> <span m="692090">and</span> <span m="692640">transitive?</span> <span m="693170">What</span> <span m="693520">kind</span> <span m="693640">of</span> <span m="693720">properties</span> <span m="694210">does</span> <span m="694400">this</span> <span m="694750">one</span> <span m="695030">have?</span> </p>
<p><span m="695970">So</span> <span m="696130">when</span> <span m="696250">we</span> <span m="696400">look</span> <span m="696620">at</span> <span m="697180">x</span> <span m="697510">is</span> <span m="697660">congruent</span> <span m="698140">to</span> <span m="698260">y</span> <span m="699320">modulo</span> <span m="699600">5,</span> <span m="699795">it</span> <span m="699990">really</span> <span m="700200">means</span> <span m="700510">that</span> <span m="700810">the</span> <span m="700980">difference</span> <span m="701470">between</span> <span m="702710">x</span> <span m="703010">and</span> <span m="703110">y</span> <span m="704890">is</span> <span m="705070">divisible</span> <span m="705570">by</span> <span m="705690">5.</span> <span m="708180">So</span> <span m="709180">is</span> <span m="709310">it</span> <span m="709400">reflexive?</span> <span m="711120">Is</span> <span m="711440">x</span> <span m="711830">congruent</span> <span m="712240">to</span> <span m="712350">x</span> <span m="712630">modulo</span> <span m="713060">5?</span> <span m="713440">It</span> <span m="713930">is</span> <span m="714120">right.</span> <span m="715020">That's</span> <span m="715860">easy.</span> <span m="716520">So</span> <span m="716740">we</span> <span m="716850">have</span> <span m="717090">yes.</span> </p>
<p><span m="718430">Now,</span> <span m="719540">if</span> <span m="719860">x</span> <span m="720260">is</span> <span m="721290">congruent</span> <span m="722020">to</span> <span m="722290">y</span> <span m="722560">module</span> <span m="723020">5,</span> <span m="724000">is</span> <span m="724210">y</span> <span m="724930">also</span> <span m="725400">congruent</span> <span m="725860">to</span> <span m="726100">x</span> <span m="726350">modulo</span> <span m="726720">5?</span> <span m="727630">It</span> <span m="727790">is</span> <span m="728210">because</span> <span m="728500">the</span> <span m="728580">difference</span> <span m="728920">between</span> <span m="729190">x</span> <span m="729410">and</span> <span m="729520">y</span> <span m="730410">is</span> <span m="730750">divisible</span> <span m="731190">by</span> <span m="731370">5</span> <span m="731860">and</span> <span m="732330">stays</span> <span m="732710">the</span> <span m="732790">same.</span> <span m="733810">So</span> <span m="734050">y</span> <span m="734220">is</span> <span m="734370">congruent</span> <span m="734830">to</span> <span m="735150">x</span> <span m="735470">as</span> <span m="735610">well.</span> <span m="736840">So</span> <span m="737330">it</span> <span m="737530">is</span> <span m="737640">symmetric.</span> </p>
<p><span m="739920">Now</span> <span m="740040">what</span> <span m="740230">about</span> <span m="740700">the</span> <span m="742380">antisymmetric?</span> <span m="744750">If</span> <span m="745240">x</span> <span m="745620">is</span> <span m="745870">congruent</span> <span m="746520">to</span> <span m="746810">y</span> <span m="747020">modulo</span> <span m="747450">5</span> <span m="748670">and</span> <span m="749110">y</span> <span m="749490">is</span> <span m="749690">congruent</span> <span m="750150">to</span> <span m="750330">x</span> <span m="750720">modulo</span> <span m="750910">5,</span> <span m="751240">does</span> <span m="751520">that</span> <span m="751580">mean</span> <span m="751720">that</span> <span m="751840">x</span> <span m="752040">is</span> <span m="752150">equal</span> <span m="752390">to</span> <span m="752520">y?</span> <span m="755340">It's</span> <span m="755430">not</span> <span m="755615">really</span> <span m="755800">true,</span> <span m="756040">right?</span> <span m="756250">You</span> <span m="756330">can</span> <span m="756470">give</span> <span m="756620">a</span> <span m="756710">counterexample</span> <span m="757460">for</span> <span m="757670">that.</span> <span m="759820">So</span> <span m="760640">for</span> <span m="760910">example,</span> <span m="761500">we</span> <span m="761660">could</span> <span m="761870">have</span> <span m="762410">that</span> <span m="764020">7</span> <span m="764930">is</span> <span m="767030">congruent</span> <span m="767670">to</span> <span m="767800">2</span> <span m="768370">modulo</span> <span m="768840">5</span> <span m="772320">and</span> <span m="779100">2</span> <span m="779240">is</span> <span m="779360">congruent</span> <span m="779740">to</span> <span m="779840">7</span> <span m="780140">modulo</span> <span m="780500">5,</span> <span m="781270">but</span> <span m="781940">they're</span> <span m="782100">not</span> <span m="782260">the</span> <span m="782340">same.</span> <span m="783220">So</span> <span m="783360">this</span> <span m="783530">is</span> <span m="783650">not</span> <span m="783840">true.</span> <span m="785690">No.</span> </p>
<p><span m="787040">What</span> <span m="787160">about</span> <span m="787380">transitivity?</span> <span m="789350">Is</span> <span m="789530">this</span> <span m="789730">true?</span> <span m="792050">So</span> <span m="793140">let's</span> <span m="793360">consider</span> <span m="793720">this</span> <span m="793920">example</span> <span m="794460">as</span> <span m="794610">well.</span> <span m="795090">So</span> <span m="795610">if</span> <span m="795830">I</span> <span m="795930">have</span> <span m="796500">that</span> <span m="797350">2</span> <span m="797650">and</span> <span m="797770">7</span> <span m="798190">are</span> <span m="798620">congruent</span> <span m="799050">to</span> <span m="799230">one</span> <span m="799380">another</span> <span m="799650">modulo</span> <span m="800030">5,</span> <span m="800850">well,</span> <span m="801290">7</span> <span m="801690">is</span> <span m="801840">also,</span> <span m="802070">for</span> <span m="802220">example,</span> <span m="802630">congruent</span> <span m="803100">to</span> <span m="803540">12</span> <span m="803940">modulo</span> <span m="804370">5.</span> <span m="807390">Does</span> <span m="807525">it</span> <span m="807660">mean</span> <span m="807860">that</span> <span m="808090">2</span> <span m="808370">and</span> <span m="808520">12</span> <span m="808920">are</span> <span m="809130">congruent</span> <span m="809580">to</span> <span m="809690">one</span> <span m="809860">another?</span> </p>
<p><span m="810420">So</span> <span m="810560">we</span> <span m="810670">have</span> <span m="810920">2</span> <span m="811930">is</span> <span m="812100">congruent</span> <span m="812530">to</span> <span m="812640">7</span> <span m="813340">modulo</span> <span m="813770">5.</span> <span m="816240">We</span> <span m="816430">have,</span> <span m="817190">say</span> <span m="817400">7</span> <span m="817850">is</span> <span m="817980">congruent</span> <span m="818480">to</span> <span m="818960">12</span> <span m="819450">modulo</span> <span m="819820">5.</span> <span m="822640">Well,</span> <span m="822790">we</span> <span m="822930">can</span> <span m="824000">look</span> <span m="824300">at</span> <span m="824430">the</span> <span m="824520">difference</span> <span m="824970">between</span> <span m="825370">2</span> <span m="825700">and</span> <span m="825870">12,</span> <span m="826980">which</span> <span m="827190">is</span> <span m="827330">10,</span> <span m="828150">is</span> <span m="828340">also</span> <span m="828560">divisible</span> <span m="829010">by</span> <span m="829180">5.</span> <span m="829440">So</span> <span m="829820">actually</span> <span m="829956">this</span> <span m="830093">does</span> <span m="830230">imply</span> <span m="830690">that</span> <span m="830890">2</span> <span m="831090">is</span> <span m="831450">congruent</span> <span m="831910">to</span> <span m="832360">12</span> <span m="832803">modulo</span> <span m="833246">5.</span> <span m="833690">Now,</span> <span m="833810">this</span> <span m="833960">is,</span> <span m="834180">of</span> <span m="834200">course,</span> <span m="834610">not</span> <span m="834635">a</span> <span m="834660">proof</span> <span m="835450">because</span> <span m="835760">this</span> <span m="835910">is</span> <span m="836110">just</span> <span m="836350">by</span> <span m="836510">example,</span> <span m="837700">but</span> <span m="837840">you</span> <span m="837900">can</span> <span m="838030">check</span> <span m="838310">for</span> <span m="838520">yourself</span> <span m="838900">that</span> <span m="839000">this</span> <span m="839290">relationship</span> <span m="839890">is</span> <span m="839990">actually</span> <span m="840620">transitive.</span> </p>
<p><span m="842600">Now,</span> <span m="842620">what</span> <span m="842730">about</span> <span m="844410">divisibility.</span> <span m="845940">Maybe</span> <span m="846080">you</span> <span m="846210">can</span> <span m="846350">help</span> <span m="846570">me</span> <span m="846650">with</span> <span m="846780">this</span> <span m="846990">one.</span> <span m="848810">So</span> <span m="849020">is</span> <span m="849170">it</span> <span m="849510">reflexive?</span> <span m="854140">Is</span> <span m="854280">this</span> <span m="854500">right?</span> <span m="854690">I</span> <span m="854840">hear</span> <span m="854990">yes.</span> <span m="855520">That's</span> <span m="855960">correct</span> <span m="856210">because</span> <span m="856530">if</span> <span m="856650">x</span> <span m="856950">and</span> <span m="857030">y</span> <span m="857270">equal</span> <span m="857480">to</span> <span m="857590">one</span> <span m="857710">another,</span> <span m="857980">well,</span> <span m="858760">it's</span> <span m="858930">1</span> <span m="859220">times</span> <span m="859660">x,</span> <span m="860060">so</span> <span m="860570">x</span> <span m="860810">divides</span> <span m="861300">x,</span> <span m="861560">so</span> <span m="861650">that's</span> <span m="861850">true.</span> <span m="863270">Is</span> <span m="863830">it</span> <span m="863950">symmetric?</span> <span m="864920">So</span> <span m="865100">if</span> <span m="865270">x</span> <span m="865630">divides</span> <span m="865990">y</span> <span m="866690">and</span> <span m="866870">y</span> <span m="867060">divides</span> <span m="867750">x,</span> <span m="871000">so</span> <span m="871290">let's</span> <span m="871510">just</span> <span m="871730">see.</span> <span m="872310">We</span> <span m="872470">are</span> <span m="872650">over</span> <span m="872950">here.</span> </p>
<p><span m="873380">So</span> <span m="873600">if</span> <span m="873770">x</span> <span m="874030">divides</span> <span m="874580">y,</span> <span m="875160">does</span> <span m="875350">that</span> <span m="875470">imply</span> <span m="875860">that</span> <span m="876030">y</span> <span m="876220">divides</span> <span m="876330">x?</span> <span m="877150">That's</span> <span m="877250">the</span> <span m="877545">relation</span> <span m="877840">that</span> <span m="877970">we</span> <span m="878080">want</span> <span m="878220">to</span> <span m="878310">check.</span> <span m="879740">Is</span> <span m="879890">that</span> <span m="880110">true?</span> <span m="880840">Not</span> <span m="881010">really.</span> <span m="881470">We</span> <span m="881590">can</span> <span m="881740">have</span> <span m="881990">like</span> <span m="882210">say</span> <span m="882400">3</span> <span m="882710">divides</span> <span m="883210">9,</span> <span m="884260">but</span> <span m="884410">9</span> <span m="884730">does</span> <span m="884970">not</span> <span m="885180">divide</span> <span m="885570">3,</span> <span m="886580">so</span> <span m="886710">this</span> <span m="886890">is</span> <span m="887020">not</span> <span m="887250">true,</span> <span m="888960">but</span> <span m="889140">antisymmetry.</span> <span m="890840">So</span> <span m="891160">if</span> <span m="891380">x</span> <span m="891710">defies</span> <span m="892230">y</span> <span m="893190">and</span> <span m="893370">also</span> <span m="893680">y</span> <span m="893890">divides</span> <span m="894000">x,</span> <span m="895560">then</span> <span m="895710">they</span> <span m="895780">must</span> <span m="896050">be</span> <span m="896180">equal</span> <span m="896390">to</span> <span m="896490">one</span> <span m="896980">another.</span> <span m="897740">So</span> <span m="901580">we</span> <span m="901680">can</span> <span m="901820">see</span> <span m="902080">that</span> <span m="902280">this</span> <span m="902680">actually</span> <span m="903130">is</span> <span m="903300">antisymmetric,</span> <span m="904150">so</span> <span m="904310">that's</span> <span m="904480">interesting.</span> </p>
<p><span m="905400">And</span> <span m="905540">transitivity,</span> <span m="906660">well,</span> <span m="906820">we</span> <span m="906920">have,</span> <span m="908510">again,</span> <span m="910190">transitivity</span> <span m="910800">because</span> <span m="911750">if</span> <span m="911900">x</span> <span m="911970">divides</span> <span m="912850">y</span> <span m="913110">and</span> <span m="913260">y</span> <span m="913450">divides</span> <span m="913560">z,</span> <span m="913870">then</span> <span m="914200">x</span> <span m="914400">also</span> <span m="914850">divides</span> <span m="914940">z.</span> <span m="915550">For</span> <span m="915710">example,</span> <span m="916450">if</span> <span m="916640">2</span> <span m="916870">divides,</span> <span m="917410">say</span> <span m="917720">4</span> <span m="918510">and</span> <span m="918660">4</span> <span m="918950">divides</span> <span m="919500">20,</span> <span m="920480">then</span> <span m="920670">2</span> <span m="920890">also</span> <span m="921170">divides</span> <span m="921630">20.</span> <span m="924570">Now</span> <span m="924800">this</span> <span m="925030">one</span> <span m="925260">over</span> <span m="925520">here</span> <span m="927010">has</span> <span m="927230">actually</span> <span m="927560">the</span> <span m="927650">same</span> <span m="927920">properties</span> <span m="928490">as</span> <span m="928930">divisibility.</span> <span m="931210">It's</span> <span m="931440">reflexive</span> <span m="933090">because</span> <span m="933630">x</span> <span m="934070">is</span> <span m="936550">at</span> <span m="936760">least</span> <span m="937140">equal</span> <span m="937380">to</span> <span m="937510">itself.</span> <span m="941240">It's</span> <span m="941460">not</span> <span m="941620">symmetric</span> <span m="942160">because</span> <span m="942960">if</span> <span m="943190">x</span> <span m="943770">is</span> <span m="943940">at</span> <span m="944030">most</span> <span m="944400">y,</span> <span m="944600">does</span> <span m="944780">not</span> <span m="944920">really</span> <span m="945160">imply</span> <span m="945540">that</span> <span m="945620">y</span> <span m="946050">is</span> <span m="946095">at</span> <span m="946140">most</span> <span m="947430">x,</span> <span m="947780">so</span> <span m="947890">this</span> <span m="948130">particular</span> <span m="948590">relation</span> <span m="949460">does</span> <span m="949680">not</span> <span m="949860">hold,</span> <span m="950620">in</span> <span m="950760">general,</span> <span m="952490">but</span> <span m="952740">it</span> <span m="952835">is,</span> <span m="952930">again,</span> <span m="953250">antisymmetric</span> <span m="953980">because</span> <span m="954370">if</span> <span m="954550">I</span> <span m="954700">have</span> <span m="954990">this</span> <span m="955170">inequality</span> <span m="955800">and</span> <span m="955900">the</span> <span m="956010">other</span> <span m="956180">one,</span> <span m="957900">well,</span> <span m="958120">x</span> <span m="958350">and</span> <span m="958430">y</span> <span m="958580">must</span> <span m="958830">be</span> <span m="958990">equal</span> <span m="959180">to</span> <span m="959300">one</span> <span m="959430">another</span> <span m="959700">in</span> <span m="959790">that</span> <span m="960000">case</span> <span m="960860">and</span> <span m="961040">transitive</span> <span m="961580">as</span> <span m="961720">well.</span> </p>
<p><span m="963280">Now,</span> <span m="963320">it</span> <span m="963360">turns</span> <span m="963660">out</span> <span m="964590">that</span> <span m="965320">in</span> <span m="965500">these</span> <span m="965720">examples,</span> <span m="966330">we</span> <span m="966440">have</span> <span m="966650">seen</span> <span m="967370">a</span> <span m="967710">certain</span> <span m="968030">combination</span> <span m="968400">of</span> <span m="968770">properties</span> <span m="970130">that</span> <span m="970250">we</span> <span m="970400">will</span> <span m="970600">be</span> <span m="971150">talking</span> <span m="971530">about.</span> <span m="972880">The</span> <span m="975220">kind</span> <span m="975430">of</span> <span m="975550">combination</span> <span m="976220">that</span> <span m="976330">we</span> <span m="976430">see</span> <span m="976740">here</span> <span m="977460">will</span> <span m="977580">lead</span> <span m="977870">to</span> <span m="978010">a</span> <span m="978080">definition</span> <span m="978820">of</span> <span m="979150">equivalence</span> <span m="979740">classes,</span> <span m="982070">equivalence</span> <span m="982590">relations,</span> <span m="985530">and</span> <span m="988610">this</span> <span m="988830">is</span> <span m="988950">also</span> <span m="989310">a</span> <span m="989360">very</span> <span m="989640">usual</span> <span m="990140">pattern,</span> <span m="992170">and</span> <span m="993520">this</span> <span m="994520">we</span> <span m="994650">will</span> <span m="994800">define</span> <span m="995270">as</span> <span m="995490">partial</span> <span m="995860">orders.</span> </p>
<p><span m="1000420">So</span> <span m="1002730">this</span> <span m="1002920">is</span> <span m="1003020">what</span> <span m="1003170">we</span> <span m="1003265">are</span> <span m="1003360">going</span> <span m="1003560">to</span> <span m="1003670">talk</span> <span m="1003940">about</span> <span m="1004260">next.</span> <span m="1005320">So</span> <span m="1005840">we'll</span> <span m="1006010">first</span> <span m="1006310">start</span> <span m="1006600">with</span> <span m="1006700">equivalence</span> <span m="1007280">relations,</span> <span m="1011630">so</span> <span m="1011970">let's</span> <span m="1012180">do</span> <span m="1012340">this.</span> <span m="1014120">What</span> <span m="1014280">is</span> <span m="1014440">an</span> <span m="1014500">equivalence</span> <span m="1015030">relation?</span> <span m="1016340">An</span> <span m="1016480">equivalence</span> <span m="1016970">relation</span> <span m="1017490">is</span> <span m="1017770">exactly</span> <span m="1018190">a</span> <span m="1018540">relation</span> <span m="1018950">that</span> <span m="1019030">has</span> <span m="1019440">those</span> <span m="1019750">few</span> <span m="1019990">properties</span> <span m="1020550">over</span> <span m="1020770">there.</span> <span m="1020950">So</span> <span m="1021080">there's</span> <span m="1021240">reflexive,</span> <span m="1021810">symmetric,</span> <span m="1022720">and</span> <span m="1022880">transitive.</span> </p>
<p><span m="1025569">So</span> <span m="1025849">an</span> <span m="1025920">equivalence</span> <span m="1028510">relation</span> <span m="1034339">is</span> <span m="1036180">reflexive</span> <span m="1038910">and</span> <span m="1039160">also</span> <span m="1039470">symmetric</span> <span m="1041980">and</span> <span m="1042250">also</span> <span m="1043619">transitive.</span> <span m="1048380">So</span> <span m="1048960">we've</span> <span m="1049190">already</span> <span m="1049510">seen</span> <span m="1049800">some</span> <span m="1050750">examples</span> <span m="1051360">up</span> <span m="1051530">there</span> <span m="1051860">or</span> <span m="1051990">one</span> <span m="1052180">example,</span> <span m="1052670">but</span> <span m="1053190">a</span> <span m="1053330">very</span> <span m="1053585">trivial</span> <span m="1054280">relation,</span> <span m="1054800">maybe</span> <span m="1055000">you</span> <span m="1055080">can</span> <span m="1055210">think</span> <span m="1055480">of</span> <span m="1055600">one</span> <span m="1055855">that</span> <span m="1056110">is</span> <span m="1056430">really</span> <span m="1056690">straightforward.</span> <span m="1059360">What</span> <span m="1059460">will</span> <span m="1059560">be</span> <span m="1059840">an</span> <span m="1060000">equivalence</span> <span m="1060290">relation</span> <span m="1060770">if</span> <span m="1060900">you</span> <span m="1061000">think</span> <span m="1061270">about</span> <span m="1062790">how</span> <span m="1063010">we</span> <span m="1063260">write</span> <span m="1063600">mathematical</span> <span m="1064160">formulas</span> <span m="1064700">down?</span> <span m="1065505">We</span> <span m="1065960">usually</span> <span m="1066240">like</span> <span m="1066400">the</span> <span m="1066500">equality</span> <span m="1066970">sign</span> <span m="1067340">also.</span> </p>
<p><span m="1067910">So</span> <span m="1068150">just</span> <span m="1068390">equality</span> <span m="1075260">the</span> <span m="1075410">equal</span> <span m="1075660">sign</span> <span m="1077250">itself</span> <span m="1077800">is</span> <span m="1078020">actually</span> <span m="1082620">one</span> <span m="1082840">example</span> <span m="1083930">and</span> <span m="1084080">the</span> <span m="1084190">other</span> <span m="1084340">example</span> <span m="1085120">is</span> <span m="1085530">the</span> <span m="1085800">one</span> <span m="1086040">that</span> <span m="1086150">we</span> <span m="1086250">have</span> <span m="1086690">there</span> <span m="1087000">and</span> <span m="1087130">that's,</span> <span m="1087360">of</span> <span m="1087470">course,</span> <span m="1087770">more</span> <span m="1087960">general.</span> <span m="1088500">We</span> <span m="1088630">can</span> <span m="1088850">have</span> <span m="1089180">x</span> <span m="1089400">is</span> <span m="1089540">congruent</span> <span m="1089970">to</span> <span m="1090100">y</span> <span m="1090350">modulo</span> <span m="1090600">n.</span> <span m="1091760">So</span> <span m="1091960">for</span> <span m="1092110">fixed</span> <span m="1092540">n,</span> <span m="1094520">we</span> <span m="1094690">have</span> <span m="1097880">another</span> <span m="1098120">equivalence</span> <span m="1098690">relation.</span> <span m="1100100">So</span> <span m="1100250">now</span> <span m="1100430">given</span> <span m="1100810">those,</span> <span m="1101390">we</span> <span m="1101540">can</span> <span m="1101690">start</span> <span m="1102010">defining</span> <span m="1102700">equivalence</span> <span m="1103130">classes.</span> </p>
<p><span m="1104390">So</span> <span m="1105670">what</span> <span m="1105820">is</span> <span m="1105930">an</span> <span m="1106010">equivalence</span> <span m="1106550">class?</span> <span m="1109020">That's</span> <span m="1109820">actually</span> <span m="1110470">everything</span> <span m="1112350">within</span> <span m="1112650">that</span> <span m="1112870">class</span> <span m="1113460">is</span> <span m="1113730">related</span> <span m="1114160">to</span> <span m="1114300">itself.</span> <span m="1115030">So</span> <span m="1115450">the</span> <span m="1115560">equivalence</span> <span m="1115980">class</span> <span m="1116450">of</span> <span m="1117280">an</span> <span m="1117470">element,</span> <span m="1117960">x</span> <span m="1118520">in</span> <span m="1118920">a</span> <span m="1121100">is</span> <span m="1121800">equal</span> <span m="1122180">to</span> <span m="1122330">the</span> <span m="1122460">set</span> <span m="1125030">of</span> <span m="1125430">all</span> <span m="1125700">the</span> <span m="1125820">elements</span> <span m="1131350">in</span> <span m="1131570">a</span> <span m="1131990">that</span> <span m="1132180">are</span> <span m="1132550">related</span> <span m="1136360">to</span> <span m="1136620">x</span> <span m="1140750">by</span> <span m="1143450">our</span> <span m="1143960">relation</span> <span m="1144520">R.</span> <span m="1145720">So</span> <span m="1145880">we</span> <span m="1146000">denote</span> <span m="1146370">this</span> <span m="1146630">equivalence</span> <span m="1147090">class.</span> <span m="1149860">So</span> <span m="1150030">this</span> <span m="1150310">is</span> <span m="1150725">denoted</span> <span m="1151140">by</span> <span m="1152330">x</span> <span m="1152630">with</span> <span m="1152810">brackets</span> <span m="1153210">around</span> <span m="1153550">it.</span> </p>
<p><span m="1154530">So</span> <span m="1154760">let's</span> <span m="1155830">put</span> <span m="1155980">it</span> <span m="1156100">into</span> <span m="1156370">a</span> <span m="1156430">formula</span> <span m="1156770">and</span> <span m="1157200">give</span> <span m="1157340">some</span> <span m="1157530">examples.</span> <span m="1158870">So</span> <span m="1160250">the</span> <span m="1160400">formula</span> <span m="1160950">for</span> <span m="1161110">this</span> <span m="1161320">in</span> <span m="1161390">mathematics</span> <span m="1162110">would</span> <span m="1162300">be</span> <span m="1163330">the</span> <span m="1163490">set</span> <span m="1164060">of</span> <span m="1164390">all</span> <span m="1164680">the</span> <span m="1164800">y</span> <span m="1165790">such</span> <span m="1166170">that</span> <span m="1167010">x</span> <span m="1167610">is</span> <span m="1168000">related</span> <span m="1168550">to</span> <span m="1168860">y.</span> <span m="1171280">So</span> <span m="1171470">as</span> <span m="1171590">an</span> <span m="1171670">example,</span> <span m="1172400">we</span> <span m="1172500">can</span> <span m="1173440">do</span> <span m="1174470">the</span> <span m="1174580">one</span> <span m="1175060">that</span> <span m="1175230">we</span> <span m="1175300">started</span> <span m="1175680">off</span> <span m="1175900">with.</span> <span m="1178500">So</span> <span m="1178740">let's</span> <span m="1178930">again</span> <span m="1179200">look</span> <span m="1179440">at</span> <span m="1179670">x</span> <span m="1181100">is</span> <span m="1181360">congruent</span> <span m="1182050">to</span> <span m="1183130">y</span> <span m="1184120">modulo</span> <span m="1184390">5</span> <span m="1186040">and</span> <span m="1186570">look</span> <span m="1186760">at</span> <span m="1187020">the</span> <span m="1187380">equivalence</span> <span m="1187800">classes.</span> </p>
<p><span m="1188300">So</span> <span m="1189070">one</span> <span m="1189250">of</span> <span m="1189380">them,</span> <span m="1189870">for</span> <span m="1189990">example,</span> <span m="1191210">we</span> <span m="1191240">could</span> <span m="1192100">look</span> <span m="1192310">at</span> <span m="1192390">the</span> <span m="1192530">equivalence</span> <span m="1192930">class</span> <span m="1193210">of</span> <span m="1193290">7.</span> <span m="1195780">We</span> <span m="1195920">were</span> <span m="1195980">looking</span> <span m="1196310">at</span> <span m="1196380">this</span> <span m="1196560">one</span> <span m="1196710">already.</span> <span m="1197060">Well,</span> <span m="1197430">what</span> <span m="1197700">are</span> <span m="1197900">all</span> <span m="1198480">the</span> <span m="1200410">y's</span> <span m="1200970">that</span> <span m="1201160">are</span> <span m="1201350">actually</span> <span m="1202410">congruence</span> <span m="1203120">to</span> <span m="1203660">7</span> <span m="1204430">modulo</span> <span m="1204920">5?</span> <span m="1206030">Well,</span> <span m="1207410">there</span> <span m="1207600">are</span> <span m="1207630">a</span> <span m="1207660">whole</span> <span m="1207920">bunch.</span> <span m="1208570">We</span> <span m="1208600">have</span> <span m="1208900">minus</span> <span m="1209370">3</span> <span m="1209910">and</span> <span m="1210235">we</span> <span m="1210560">have</span> <span m="1210820">2,</span> <span m="1211930">7,</span> <span m="1213420">we</span> <span m="1213510">have</span> <span m="1213710">12,</span> <span m="1215310">17,</span> <span m="1215768">and</span> <span m="1216226">22,</span> <span m="1218210">and</span> <span m="1218370">so</span> <span m="1218590">on.</span> <span m="1218750">And</span> <span m="1218840">we</span> <span m="1218930">add</span> <span m="1219190">5</span> <span m="1219620">to</span> <span m="1219830">all</span> <span m="1220110">these</span> <span m="1220480">and</span> <span m="1220850">this</span> <span m="1221790">is</span> <span m="1222260">the</span> <span m="1222350">equivalence</span> <span m="1222920">class</span> <span m="1223105">that</span> <span m="1223290">belongs</span> <span m="1223720">to</span> <span m="1223840">7.</span> </p>
<p><span m="1224850">Now</span> <span m="1224980">notice</span> <span m="1226050">that</span> <span m="1226140">the</span> <span m="1226250">equivalence</span> <span m="1226690">class</span> <span m="1227020">of</span> <span m="1227110">7</span> <span m="1227900">is</span> <span m="1228090">actually</span> <span m="1228450">equal</span> <span m="1229290">to</span> <span m="1229530">the</span> <span m="1229650">equivalence</span> <span m="1230120">class</span> <span m="1230590">of</span> <span m="1230820">12.</span> <span m="1232460">It's</span> <span m="1232670">the</span> <span m="1232750">same</span> <span m="1233040">set.</span> <span m="1234750">Everything</span> <span m="1235210">that</span> <span m="1235280">is</span> <span m="1235350">congruent</span> <span m="1235740">to</span> <span m="1235880">12</span> <span m="1236650">modulo</span> <span m="1236980">5</span> <span m="1237380">is</span> <span m="1237490">also</span> <span m="1237750">congruent</span> <span m="1238250">to</span> <span m="1238350">7</span> <span m="1238720">module</span> <span m="1239090">5</span> <span m="1240550">and</span> <span m="1240770">this</span> <span m="1240920">is,</span> <span m="1241050">again,</span> <span m="1241330">equal</span> <span m="1241730">to</span> <span m="1241880">say,</span> <span m="1242130">17,</span> <span m="1243830">and</span> <span m="1244210">so</span> <span m="1244430">on.</span> </p>
<p><span m="1249670">So</span> <span m="1250990">now</span> <span m="1251260">we</span> <span m="1251420">can</span> <span m="1251990">start</span> <span m="1252200">talking</span> <span m="1252590">about</span> <span m="1252890">a</span> <span m="1252980">nice</span> <span m="1253280">property</span> <span m="1253780">that</span> <span m="1254440">equivalence</span> <span m="1255000">classes</span> <span m="1255480">have,</span> <span m="1256660">which</span> <span m="1256930">is</span> <span m="1257060">that</span> <span m="1257220">the</span> <span m="1257350">equivalence</span> <span m="1257730">classes</span> <span m="1258090">together</span> <span m="1258600">partition</span> <span m="1259170">the</span> <span m="1259240">set</span> <span m="1259560">A.</span> <span m="1260230">So</span> <span m="1260730">I</span> <span m="1260820">will</span> <span m="1260910">need</span> <span m="1261100">to</span> <span m="1261220">define</span> <span m="1262020">first</span> <span m="1262880">what</span> <span m="1262980">a</span> <span m="1263080">partition</span> <span m="1263350">is.</span> <span m="1265270">And</span> <span m="1267280">it's</span> <span m="1267510">defined</span> <span m="1267870">as</span> <span m="1268010">follows.</span> <span m="1268530">A</span> <span m="1268590">partition</span> <span m="1270430">of</span> <span m="1270650">A</span> <span m="1272750">is</span> <span m="1273780">a</span> <span m="1273950">collection</span> <span m="1278390">of</span> <span m="1278760">this</span> <span m="1279040">joint</span> <span m="1283290">non-empty</span> <span m="1283900">sets</span> <span m="1294520">A1</span> <span m="1297230">up</span> <span m="1297420">to</span> <span m="1297650">An</span> <span m="1299380">and</span> <span m="1299600">they're</span> <span m="1299790">all</span> <span m="1299980">subsets</span> <span m="1300670">of</span> <span m="1303000">A.</span> <span m="1304010">And</span> <span m="1304780">the</span> <span m="1304940">union</span> <span m="1305950">of</span> <span m="1306120">all</span> <span m="1306440">of</span> <span m="1306540">those</span> <span m="1307300">is</span> <span m="1307460">actually</span> <span m="1307850">equal</span> <span m="1308070">to</span> <span m="1308160">the</span> <span m="1308270">set</span> <span m="1308620">A.</span> <span m="1310270">So</span> <span m="1310470">who's</span> <span m="1310670">union</span> <span m="1312390">is</span> <span m="1312690">A.</span> </p>
<p><span m="1314110">So</span> <span m="1314300">let's</span> <span m="1314520">have</span> <span m="1314690">a</span> <span m="1314750">look,</span> <span m="1314900">again,</span> <span m="1315190">at</span> <span m="1315280">this</span> <span m="1315480">example</span> <span m="1315890">and</span> <span m="1316280">see</span> <span m="1316500">whether</span> <span m="1316690">we</span> <span m="1316880">can</span> <span m="1317130">figure</span> <span m="1317490">out</span> <span m="1317650">what</span> <span m="1318790">the</span> <span m="1318890">equivalence</span> <span m="1319320">classes</span> <span m="1319770">are.</span> <span m="1321700">So</span> <span m="1321850">the</span> <span m="1321910">example</span> <span m="1322190">is,</span> <span m="1323600">well,</span> <span m="1323920">we</span> <span m="1324140">can</span> <span m="1324350">have</span> <span m="1325400">everything</span> <span m="1325940">that</span> <span m="1326100">this</span> <span m="1326300">actually</span> <span m="1326470">a</span> <span m="1326640">multiple</span> <span m="1327080">of</span> <span m="1327160">5.</span> <span m="1328110">That's</span> <span m="1328570">this</span> <span m="1328770">one</span> <span m="1329990">class.</span> <span m="1330320">So</span> <span m="1330650">we</span> <span m="1330780">have</span> <span m="1331040">minus</span> <span m="1331470">5,</span> <span m="1331918">0,</span> <span m="1332814">5,</span> <span m="1333710">10,</span> <span m="1334490">and</span> <span m="1334620">we</span> <span m="1334750">go</span> <span m="1334940">all</span> <span m="1335120">the</span> <span m="1335200">way</span> <span m="1335400">up.</span> </p>
<p><span m="1336790">Another</span> <span m="1337160">equivalence</span> <span m="1337680">class</span> <span m="1338080">is,</span> <span m="1338940">well,</span> <span m="1340620">we</span> <span m="1340740">just</span> <span m="1341020">add</span> <span m="1341910">1</span> <span m="1342360">to</span> <span m="1342580">each</span> <span m="1342850">of</span> <span m="1342970">those</span> <span m="1343200">elements</span> <span m="1343620">here,</span> <span m="1344140">so</span> <span m="1344490">if</span> <span m="1344620">minus</span> <span m="1345060">4</span> <span m="1345310">is</span> <span m="1345520">congruent</span> <span m="1345990">to</span> <span m="1346110">1,</span> <span m="1346533">modulo</span> <span m="1346956">5</span> <span m="1347380">is</span> <span m="1347520">congruent</span> <span m="1347890">to</span> <span m="1348000">6,</span> <span m="1348356">modulo</span> <span m="1348712">5</span> <span m="1349600">congruent</span> <span m="1349910">to</span> <span m="1350110">11,</span> <span m="1351460">and</span> <span m="1351670">so</span> <span m="1351900">on.</span> <span m="1352590">And</span> <span m="1352700">so</span> <span m="1352850">we</span> <span m="1352960">can</span> <span m="1353110">continue</span> <span m="1354000">and</span> <span m="1354140">we</span> <span m="1354230">actually</span> <span m="1354660">see</span> <span m="1355630">that</span> <span m="1355820">we</span> <span m="1356010">minus</span> <span m="1356460">3</span> <span m="1356610">is</span> <span m="1356730">congruent</span> <span m="1357110">to</span> <span m="1357220">2,</span> <span m="1358330">to</span> <span m="1358520">7,</span> <span m="1359810">to</span> <span m="1359970">12,</span> <span m="1360530">and</span> <span m="1360680">so</span> <span m="1360880">on.</span> <span m="1361230">That's</span> <span m="1361310">the</span> <span m="1361390">one</span> <span m="1361560">we</span> <span m="1361660">had</span> <span m="1362680">up</span> <span m="1362850">there.</span> </p>
<p><span m="1364630">Another</span> <span m="1364990">one</span> <span m="1365200">is</span> <span m="1365930">minus</span> <span m="1366350">2,</span> <span m="1368710">3,</span> <span m="1369594">8,</span> <span m="1371362">13,</span> <span m="1373320">and</span> <span m="1374270">we</span> <span m="1374500">have</span> <span m="1375310">minus</span> <span m="1375760">1,</span> <span m="1376730">4,</span> <span m="1378185">9,</span> <span m="1379155">14,</span> <span m="1380130">and</span> <span m="1380310">so</span> <span m="1380440">forth.</span> <span m="1381760">So</span> <span m="1382370">these</span> <span m="1382570">are</span> <span m="1382630">all</span> <span m="1382790">the</span> <span m="1382900">equivalence</span> <span m="1383320">classes</span> <span m="1383880">because</span> <span m="1384840">now</span> <span m="1384990">we</span> <span m="1385120">look</span> <span m="1385330">around.</span> <span m="1385900">If</span> <span m="1386070">we</span> <span m="1386240">add</span> <span m="1386610">one</span> <span m="1386930">more</span> <span m="1387200">2</span> <span m="1387360">minus</span> <span m="1387750">1,</span> <span m="1387920">we</span> <span m="1388030">get</span> <span m="1389150">0.</span> <span m="1390380">So</span> <span m="1390540">we</span> <span m="1390650">get</span> <span m="1390780">0,</span> <span m="1391227">5,</span> <span m="1391674">15,</span> <span m="1392570">and</span> <span m="1392670">so</span> <span m="1392850">on</span> <span m="1393440">and</span> <span m="1393620">that's</span> <span m="1393830">exactly</span> <span m="1394250">the</span> <span m="1394340">same</span> <span m="1394590">class</span> <span m="1394960">as</span> <span m="1395070">this</span> <span m="1395260">one.</span> <span m="1395980">So</span> <span m="1396720">we</span> <span m="1396820">see</span> <span m="1397150">that</span> <span m="1398850">for</span> <span m="1399890">this</span> <span m="1400020">particular</span> <span m="1400370">example,</span> <span m="1401220">we</span> <span m="1401260">notice</span> <span m="1401760">that</span> <span m="1402760">these</span> <span m="1402940">equivalence</span> <span m="1403440">classes</span> <span m="1404770">are</span> <span m="1405040">a</span> <span m="1405120">partition</span> <span m="1405940">of</span> <span m="1406230">all</span> <span m="1406460">the</span> <span m="1406570">integers.</span> </p>
<p><span m="1407980">Turns</span> <span m="1408350">out</span> <span m="1408510">that</span> <span m="1408580">this</span> <span m="1408800">is</span> <span m="1408940">a</span> <span m="1408990">general</span> <span m="1410640">property</span> <span m="1412150">and</span> <span m="1413160">we're</span> <span m="1413520">not</span> <span m="1414060">going</span> <span m="1414290">to</span> <span m="1414410">prove</span> <span m="1414770">this.</span> <span m="1416090">That's</span> <span m="1416280">pretty</span> <span m="1416580">straightforward,</span> <span m="1417420">so</span> <span m="1417560">you</span> <span m="1417660">should</span> <span m="1417890">actually</span> <span m="1418680">think</span> <span m="1418960">about</span> <span m="1419130">it</span> <span m="1419300">yourself.</span> <span m="1421860">Let's</span> <span m="1422330">keep</span> <span m="1422650">this</span> <span m="1422890">up</span> <span m="1423130">here</span> <span m="1424830">and</span> <span m="1426890">take</span> <span m="1427110">this</span> <span m="1427370">out.</span> <span m="1434070">So</span> <span m="1434230">the</span> <span m="1434340">theorem</span> <span m="1434780">is</span> <span m="1434990">that</span> <span m="1436910">every</span> <span m="1437190">equivalence</span> <span m="1437850">relation</span> <span m="1439800">on</span> <span m="1440020">a</span> <span m="1440445">set</span> <span m="1440586">A</span> <span m="1440728">can</span> <span m="1440870">be</span> <span m="1441030">partitioned</span> <span m="1441590">in</span> <span m="1441720">its</span> <span m="1442490">questions</span> <span m="1442890">classes.</span> <span m="1444220">So</span> <span m="1444480">the</span> <span m="1444590">theorem</span> <span m="1445280">is</span> <span m="1449040">the</span> <span m="1449360">equivalence</span> <span m="1450000">class</span> <span m="1463500">of</span> <span m="1464590">an</span> <span m="1464670">equivalence</span> <span m="1465090">relation</span> <span m="1473110">on</span> <span m="1473350">a</span> <span m="1473410">set</span> <span m="1473700">A</span> <span m="1478190">form</span> <span m="1478880">a</span> <span m="1479090">partition</span> <span m="1485310">of</span> <span m="1485560">A.</span> </p>
<p><span m="1486970">Now,</span> <span m="1487090">I'm</span> <span m="1487160">not</span> <span m="1487310">going</span> <span m="1487480">to</span> <span m="1487530">prove</span> <span m="1487890">this.</span> <span m="1489590">It's</span> <span m="1489750">actually</span> <span m="1490020">really</span> <span m="1490210">straightforward.</span> <span m="1491430">You</span> <span m="1491610">should</span> <span m="1491810">really</span> <span m="1492030">look</span> <span m="1492240">at</span> <span m="1492350">this</span> <span m="1493190">and</span> <span m="1493340">see</span> <span m="1493510">that</span> <span m="1493700">you</span> <span m="1493810">can</span> <span m="1494410">prove</span> <span m="1494700">this</span> <span m="1494890">with</span> <span m="1495080">the</span> <span m="1495170">properties,</span> <span m="1495810">the</span> <span m="1495920">property</span> <span m="1496250">definitions,</span> <span m="1496990">and</span> <span m="1497470">the</span> <span m="1497540">definition</span> <span m="1498050">of</span> <span m="1498180">an</span> <span m="1498250">equivalence</span> <span m="1498740">relation.</span> <span m="1500260">So</span> <span m="1500700">this</span> <span m="1500890">is</span> <span m="1500970">as</span> <span m="1501250">far</span> <span m="1501351">as</span> <span m="1501453">we</span> <span m="1501555">go</span> <span m="1501860">is</span> <span m="1501960">equivalence</span> <span m="1502440">relations.</span> <span m="1503720">And</span> <span m="1503860">so</span> <span m="1503990">now</span> <span m="1504460">we</span> <span m="1504560">will</span> <span m="1504860">continue</span> <span m="1505340">with</span> <span m="1505820">partial</span> <span m="1506200">orders.</span> <span m="1507040">Again,</span> <span m="1507330">we</span> <span m="1507750">go</span> <span m="1507920">through</span> <span m="1508770">a</span> <span m="1508830">few</span> <span m="1509060">definitions</span> <span m="1510000">and</span> <span m="1510170">then</span> <span m="1510300">at</span> <span m="1510400">some</span> <span m="1510600">point,</span> <span m="1511490">we'll</span> <span m="1511590">be</span> <span m="1511780">able</span> <span m="1511930">to</span> <span m="1512050">prove</span> <span m="1512290">a</span> <span m="1512390">few</span> <span m="1512490">interesting</span> <span m="1513020">properties.</span> </p>
<p><span m="1515280">So</span> <span m="1515370">let's</span> <span m="1515590">talk</span> <span m="1515830">about</span> <span m="1516560">partial</span> <span m="1517000">orders.</span> <span m="1520730">So</span> <span m="1521010">notice</span> <span m="1521530">that</span> <span m="1522320">we</span> <span m="1522530">have</span> <span m="1522680">shifted</span> <span m="1523180">now</span> <span m="1524290">from</span> <span m="1525260">in</span> <span m="1525410">this</span> <span m="1525810">diagram</span> <span m="1526290">over</span> <span m="1526580">here,</span> <span m="1526910">in</span> <span m="1527000">this</span> <span m="1527200">table,</span> <span m="1528250">from</span> <span m="1529790">this</span> <span m="1530030">pattern</span> <span m="1530380">that</span> <span m="1530530">you</span> <span m="1530750">were</span> <span m="1530810">first</span> <span m="1531120">interested</span> <span m="1531630">in.</span> <span m="1531780">Now,</span> <span m="1531930">we</span> <span m="1532085">go</span> <span m="1532240">to</span> <span m="1532340">partial</span> <span m="1532740">orders</span> <span m="1533210">and</span> <span m="1533300">the</span> <span m="1533370">difference</span> <span m="1533760">is</span> <span m="1533890">going</span> <span m="1534120">to</span> <span m="1534250">be</span> <span m="1534950">that</span> <span m="1536290">we</span> <span m="1536730">do</span> <span m="1536830">not</span> <span m="1537050">have</span> <span m="1537260">symmetry,</span> <span m="1538270">but</span> <span m="1538470">we</span> <span m="1538670">do</span> <span m="1538860">have</span> <span m="1539090">antisymmetry</span> <span m="1540380">and</span> <span m="1540550">that</span> <span m="1540750">brings</span> <span m="1541050">out</span> <span m="1541420">a</span> <span m="1541520">whole</span> <span m="1541820">different</span> <span m="1542800">structure.</span> </p>
<p><span m="1545110">So</span> <span m="1546510">a</span> <span m="1547850">relation</span> <span m="1550920">is--</span> <span m="1554100">it's</span> <span m="1554180">in</span> <span m="1554390">brackets</span> <span m="1554860">I</span> <span m="1554930">put</span> <span m="1555170">here--</span> <span m="1555460">weak,</span> <span m="1556900">I'll</span> <span m="1557110">explain</span> <span m="1557540">in</span> <span m="1557660">a</span> <span m="1557930">moment</span> <span m="1558200">why</span> <span m="1558246">I</span> <span m="1558293">do</span> <span m="1558340">this.</span> <span m="1559520">It's</span> <span m="1559720">a</span> <span m="1559760">weak</span> <span m="1560060">partial</span> <span m="1560550">order</span> <span m="1570730">if</span> <span m="1570950">it</span> <span m="1571060">is</span> <span m="1571780">reflexive,</span> <span m="1574590">and</span> <span m="1575060">antisymmetric</span> <span m="1576300">and</span> <span m="1576490">transitive.</span> <span m="1588840">So</span> <span m="1589090">why</span> <span m="1589290">do</span> <span m="1589530">I</span> <span m="1589700">put</span> <span m="1590410">weak</span> <span m="1590650">up</span> <span m="1590870">here?</span> <span m="1592020">Well,</span> <span m="1592220">if</span> <span m="1592330">you</span> <span m="1592450">look</span> <span m="1592590">in</span> <span m="1592790">the</span> <span m="1592890">book,</span> <span m="1593250">there</span> <span m="1593430">are</span> <span m="1593610">two</span> <span m="1593760">definitions,</span> <span m="1594700">one</span> <span m="1594780">is</span> <span m="1595130">a</span> <span m="1595500">weak</span> <span m="1595770">partial</span> <span m="1596170">order,</span> <span m="1597110">which</span> <span m="1597380">is</span> <span m="1599100">with</span> <span m="1600430">reflexivity</span> <span m="1602200">and</span> <span m="1602360">another</span> <span m="1602580">one</span> <span m="1602820">is</span> <span m="1603210">a</span> <span m="1603600">strong</span> <span m="1604000">partial</span> <span m="1604450">order.</span> <span m="1605230">And</span> <span m="1605430">that</span> <span m="1605620">one</span> <span m="1607180">has</span> <span m="1608130">a</span> <span m="1608230">property</span> <span m="1608780">that</span> <span m="1609000">I</span> <span m="1609070">did</span> <span m="1609210">not</span> <span m="1609420">talk</span> <span m="1609650">about</span> <span m="1609940">here</span> <span m="1610310">called</span> <span m="1610650">irreflexibility</span> <span m="1612240">and</span> <span m="1612440">it's</span> <span m="1612580">something</span> <span m="1612960">that</span> <span m="1614250">I</span> <span m="1614400">will</span> <span m="1614510">not</span> <span m="1614670">talk</span> <span m="1614880">about</span> <span m="1615110">in</span> <span m="1615190">this</span> <span m="1615350">lecture,</span> <span m="1615650">but</span> <span m="1615740">you</span> <span m="1615780">should</span> <span m="1616030">read</span> <span m="1616210">about</span> <span m="1616540">it</span> <span m="1617170">and</span> <span m="1617440">all</span> <span m="1617640">these</span> <span m="1617860">properties,</span> <span m="1618420">all</span> <span m="1618570">the</span> <span m="1618690">theorems</span> <span m="1619040">that</span> <span m="1619340">we</span> <span m="1619550">talk</span> <span m="1619840">about</span> <span m="1620120">right</span> <span m="1620370">now</span> <span m="1620680">also</span> <span m="1621040">hold</span> <span m="1621950">for</span> <span m="1622090">the</span> <span m="1622360">strong</span> <span m="1622390">version</span> <span m="1622420">of</span> <span m="1622450">a</span> <span m="1622480">partial</span> <span m="1622950">order.</span> </p>
<p><span m="1624250">But</span> <span m="1624420">for</span> <span m="1624540">now,</span> <span m="1625400">let's</span> <span m="1625480">just</span> <span m="1627950">call</span> <span m="1628340">partial</span> <span m="1628730">orders</span> <span m="1629280">those</span> <span m="1629820">that</span> <span m="1629930">are</span> <span m="1630050">reflexive,</span> <span m="1631410">antisymmetric,</span> <span m="1632045">and</span> <span m="1632400">transitive.</span> <span m="1635420">Well,</span> <span m="1635700">we</span> <span m="1635840">already</span> <span m="1636140">saw</span> <span m="1636380">a</span> <span m="1636470">few</span> <span m="1637390">examples</span> <span m="1638100">up</span> <span m="1638240">here.</span> <span m="1639720">We</span> <span m="1639850">have</span> <span m="1640600">divisibility,</span> <span m="1642280">which</span> <span m="1642890">has</span> <span m="1643110">this</span> <span m="1643290">property</span> <span m="1644750">and</span> <span m="1645530">also</span> <span m="1649160">the</span> <span m="1649240">less</span> <span m="1649440">than</span> <span m="1649580">or</span> <span m="1649690">equal</span> <span m="1650420">relationship.</span> </p>
<p><span m="1655420">Now</span> <span m="1655650">usually</span> <span m="1656510">what</span> <span m="1656650">we</span> <span m="1656800">do</span> <span m="1657130">is,</span> <span m="1657490">instead</span> <span m="1658030">of</span> <span m="1658130">using</span> <span m="1659070">a</span> <span m="1659210">capital</span> <span m="1659700">letter</span> <span m="1660020">R,</span> <span m="1660970">we</span> <span m="1661130">will</span> <span m="1661280">use</span> <span m="1661790">a</span> <span m="1662210">relation</span> <span m="1662700">symbol.</span> <span m="1663470">So</span> <span m="1664630">a</span> <span m="1664710">partial</span> <span m="1665310">order</span> <span m="1666660">relation</span> <span m="1674840">is</span> <span m="1675400">denoted</span> <span m="1676340">differently,</span> <span m="1678550">is</span> <span m="1678780">denoted</span> <span m="1681850">with</span> <span m="1685020">something</span> <span m="1685410">like</span> <span m="1685590">that</span> <span m="1687340">instead</span> <span m="1687870">of</span> <span m="1692000">R.</span> <span m="1693780">Now</span> <span m="1693900">the</span> <span m="1693990">reason</span> <span m="1694270">for</span> <span m="1694470">that</span> <span m="1694710">is</span> <span m="1694920">because</span> <span m="1695410">we</span> <span m="1695990">have</span> <span m="1697560">actually</span> <span m="1699950">will</span> <span m="1700150">show</span> <span m="1700850">that</span> <span m="1701310">there's</span> <span m="1701640">a</span> <span m="1701710">partial</span> <span m="1702140">order,</span> <span m="1702450">so</span> <span m="1706050">this</span> <span m="1706270">name</span> <span m="1706710">does</span> <span m="1706800">not</span> <span m="1706890">come</span> <span m="1706980">by</span> <span m="1707150">itself.</span> <span m="1708990">It</span> <span m="1709130">turns</span> <span m="1709460">out</span> <span m="1709640">that</span> <span m="1709730">we</span> <span m="1710070">can</span> <span m="1710173">give</span> <span m="1710276">an</span> <span m="1710380">order</span> <span m="1710655">to</span> <span m="1711722">the</span> <span m="1712120">order</span> <span m="1712360">ranking</span> <span m="1712910">to</span> <span m="1713020">the</span> <span m="1713160">elements,</span> <span m="1713890">one</span> <span m="1714390">element</span> <span m="1714780">is</span> <span m="1714910">less</span> <span m="1715100">than</span> <span m="1715220">another</span> <span m="1715670">and</span> <span m="1715900">so</span> <span m="1716100">on.</span> </p>
<p><span m="1717200">So</span> <span m="1720070">let's</span> <span m="1721840">keep</span> <span m="1722130">this</span> <span m="1722360">over</span> <span m="1722650">here</span> <span m="1724510">and</span> <span m="1725910">change</span> <span m="1726630">up</span> <span m="1726830">here.</span> <span m="1729890">So</span> <span m="1730730">an</span> <span m="1731210">example</span> <span m="1734990">that</span> <span m="1735190">we</span> <span m="1735280">will</span> <span m="1735460">talk</span> <span m="1735750">about</span> <span m="1736130">in</span> <span m="1736200">the</span> <span m="1736290">moment,</span> <span m="1737600">but</span> <span m="1737720">first</span> <span m="1738100">let</span> <span m="1738280">me</span> <span m="1739260">introduce</span> <span m="1739730">some</span> <span m="1739780">more</span> <span m="1739960">notations.</span> <span m="1740570">So</span> <span m="1742780">we</span> <span m="1742920">call</span> <span m="1746190">the</span> <span m="1746320">pair</span> <span m="1746800">A</span> <span m="1746995">with</span> <span m="1747190">this</span> <span m="1747530">relationship</span> <span m="1748980">symbol</span> <span m="1752240">is</span> <span m="1752490">actually</span> <span m="1752900">called</span> <span m="1754820">a</span> <span m="1755310">partially</span> <span m="1755780">ordered</span> <span m="1756130">set.</span> <span m="1763480">And</span> <span m="1766360">we</span> <span m="1766580">also</span> <span m="1767270">abbreviate</span> <span m="1767840">this</span> <span m="1768870">by</span> <span m="1768970">calling</span> <span m="1769370">it</span> <span m="1769570">a</span> <span m="1769730">poset.</span> </p>
<p><span m="1774840">Now,</span> <span m="1775050">in</span> <span m="1775140">a</span> <span m="1775280">poset,</span> <span m="1775860">again,</span> <span m="1776270">can</span> <span m="1776470">be</span> <span m="1776570">described</span> <span m="1777300">by</span> <span m="1777490">means</span> <span m="1777880">of</span> <span m="1778120">a</span> <span m="1778220">directed</span> <span m="1778560">graph,</span> <span m="1780400">so</span> <span m="1781320">we</span> <span m="1781470">can</span> <span m="1781640">do</span> <span m="1781780">that</span> <span m="1781980">as</span> <span m="1782140">well.</span> <span m="1785980">So</span> <span m="1786250">poset</span> <span m="1786590">is</span> <span m="1786800">a</span> <span m="1786860">directed</span> <span m="1787360">graph</span> <span m="1791690">such</span> <span m="1792110">that</span> <span m="1794140">it</span> <span m="1794380">has</span> <span m="1795300">the</span> <span m="1795590">vertex</span> <span m="1796150">set</span> <span m="1797606">A</span> <span m="1800050">and</span> <span m="1800780">the</span> <span m="1800840">edge</span> <span m="1800900">set</span> <span m="1801360">is</span> <span m="1801540">defined</span> <span m="1802110">by</span> <span m="1802940">the</span> <span m="1803110">relationship.</span> <span m="1804060">So</span> <span m="1805830">the</span> <span m="1806020">edge</span> <span m="1806305">set</span> <span m="1808360">is</span> <span m="1808900">actually</span> <span m="1810160">this</span> <span m="1810440">thing.</span> </p>
<p><span m="1811010">Notice</span> <span m="1811270">that</span> <span m="1811910">in</span> <span m="1812060">our</span> <span m="1812190">definition,</span> <span m="1812445">this</span> <span m="1812700">is</span> <span m="1812920">actually</span> <span m="1813100">a</span> <span m="1813280">set,</span> <span m="1813720">right?</span> <span m="1814040">It's</span> <span m="1814210">still</span> <span m="1814450">a</span> <span m="1814520">set.</span> <span m="1817580">It's</span> <span m="1817770">a</span> <span m="1817820">set</span> <span m="1818040">of</span> <span m="1818190">tuples,</span> <span m="1819300">of</span> <span m="1819660">pairs,</span> <span m="1821780">and</span> <span m="1822950">we</span> <span m="1823070">can,</span> <span m="1823230">again,</span> <span m="1824050">create</span> <span m="1824420">a</span> <span m="1824460">directed</span> <span m="1824930">graph</span> <span m="1826020">by</span> <span m="1826160">using</span> <span m="1826520">this,</span> <span m="1826820">so</span> <span m="1827160">nothing</span> <span m="1827450">has</span> <span m="1827630">changed.</span> <span m="1828690">But</span> <span m="1828920">for</span> <span m="1829450">posets,</span> <span m="1830170">we</span> <span m="1830300">can</span> <span m="1830540">actually</span> <span m="1832530">create</span> <span m="1833770">a</span> <span m="1833860">more</span> <span m="1834800">sort</span> <span m="1835110">of</span> <span m="1835530">easier</span> <span m="1835950">to</span> <span m="1836170">read</span> <span m="1838370">sort</span> <span m="1838530">of</span> <span m="1838890">representation,</span> <span m="1839740">which</span> <span m="1839950">we'll</span> <span m="1840080">call</span> <span m="1840470">a</span> <span m="1840650">Hesse</span> <span m="1841150">diagram,</span> <span m="1843210">which</span> <span m="1843390">is</span> <span m="1843490">also</span> <span m="1843820">a</span> <span m="1843880">graph</span> <span m="1844870">and</span> <span m="1845290">let</span> <span m="1845430">me</span> <span m="1845500">give</span> <span m="1845670">an</span> <span m="1845760">example</span> <span m="1846270">to</span> <span m="1846390">explain</span> <span m="1846870">how</span> <span m="1847030">that</span> <span m="1847200">works.</span> </p>
<p><span m="1851460">So</span> <span m="1852450">I</span> <span m="1852560">think</span> <span m="1852840">we</span> <span m="1852930">can</span> <span m="1853140">take</span> <span m="1853400">this</span> <span m="1853670">out.</span> <span m="1857436">So</span> <span m="1857890">the</span> <span m="1857960">example</span> <span m="1858550">is,</span> <span m="1859240">imagine</span> <span m="1861300">that</span> <span m="1863280">a</span> <span m="1863440">guy</span> <span m="1863665">is</span> <span m="1863890">going</span> <span m="1864140">to</span> <span m="1864280">dress</span> <span m="1864660">up</span> <span m="1864860">for</span> <span m="1865600">something</span> <span m="1866000">very</span> <span m="1866220">formal.</span> <span m="1867430">So</span> <span m="1867620">how</span> <span m="1867740">does</span> <span m="1867890">he</span> <span m="1867980">start</span> <span m="1868310">out?</span> <span m="1870020">So</span> <span m="1870340">let's</span> <span m="1871490">have</span> <span m="1871810">as</span> <span m="1872040">vertices</span> <span m="1872750">in</span> <span m="1872920">the</span> <span m="1873010">graph,</span> <span m="1873830">in</span> <span m="1873940">this</span> <span m="1874110">diagram</span> <span m="1875590">or</span> <span m="1876220">the</span> <span m="1876340">elements</span> <span m="1876810">of</span> <span m="1877000">A</span> <span m="1878000">is</span> <span m="1878190">going</span> <span m="1878370">to</span> <span m="1878470">be</span> <span m="1878650">all</span> <span m="1879850">items</span> <span m="1880320">that</span> <span m="1880430">he</span> <span m="1880600">will</span> <span m="1880820">start</span> <span m="1881690">to</span> <span m="1881840">put</span> <span m="1882040">on</span> <span m="1882210">and</span> <span m="1882400">start</span> <span m="1882590">wearing,</span> <span m="1882780">so</span> <span m="1883070">his</span> <span m="1883430">pants,</span> <span m="1883790">his</span> <span m="1884000">shirt,</span> <span m="1884460">and</span> <span m="1884610">so</span> <span m="1884810">on.</span> <span m="1884990">So</span> <span m="1885920">let's</span> <span m="1886150">have</span> <span m="1886290">a</span> <span m="1886370">look.</span> </p>
<p><span m="1887250">So</span> <span m="1888110">what</span> <span m="1888200">do</span> <span m="1888240">you</span> <span m="1888360">start</span> <span m="1888650">off</span> <span m="1888880">with?</span> <span m="1890620">Well,</span> <span m="1891070">maybe</span> <span m="1891320">your</span> <span m="1891470">underwear</span> <span m="1892230">would</span> <span m="1892370">be</span> <span m="1892480">a</span> <span m="1892520">good</span> <span m="1892750">idea.</span> <span m="1896300">So</span> <span m="1896490">this</span> <span m="1896730">could</span> <span m="1896890">be</span> <span m="1897100">a</span> <span m="1897180">first</span> <span m="1898555">item</span> <span m="1898820">that</span> <span m="1898870">you</span> <span m="1898920">want</span> <span m="1899060">to</span> <span m="1899150">put</span> <span m="1899390">on.</span> <span m="1899620">So</span> <span m="1899770">let's</span> <span m="1900620">have</span> <span m="1901000">the</span> <span m="1901120">relation</span> <span m="1901435">that</span> <span m="1901750">we</span> <span m="1902040">are</span> <span m="1902180">interested</span> <span m="1902740">in</span> <span m="1903220">to</span> <span m="1903350">be</span> <span m="1903560">one</span> <span m="1904770">where</span> <span m="1904960">we</span> <span m="1905060">say,</span> <span m="1905300">well,</span> <span m="1905590">I</span> <span m="1905720">first</span> <span m="1906150">need</span> <span m="1906250">to</span> <span m="1906340">put</span> <span m="1906510">on</span> <span m="1906610">my</span> <span m="1906770">underwear</span> <span m="1907610">and</span> <span m="1907800">only</span> <span m="1908080">after</span> <span m="1908470">that</span> <span m="1908850">I</span> <span m="1909020">can</span> <span m="1909230">put</span> <span m="1909510">on</span> <span m="1910350">my</span> <span m="1910480">pants,</span> <span m="1911080">for</span> <span m="1911370">example.</span> <span m="1913130">So</span> <span m="1913300">that</span> <span m="1913460">makes</span> <span m="1913700">sense</span> <span m="1913980">too.</span> <span m="1915150">And</span> <span m="1915540">since</span> <span m="1916020">I'm</span> <span m="1916160">doing</span> <span m="1916360">something</span> <span m="1916740">very</span> <span m="1916940">formal</span> <span m="1917600">later</span> <span m="1917920">on,</span> <span m="1918400">I</span> <span m="1918510">better</span> <span m="1918780">first</span> <span m="1919130">put</span> <span m="1919270">on</span> <span m="1919420">my</span> <span m="1919530">shirt</span> <span m="1921570">because</span> <span m="1921950">I</span> <span m="1921970">like</span> <span m="1922150">to</span> <span m="1922280">tuck</span> <span m="1922510">that</span> <span m="1922670">into</span> <span m="1922940">my</span> <span m="1923100">pants,</span> <span m="1924980">but</span> <span m="1925210">it's</span> <span m="1925360">not</span> <span m="1925470">really</span> <span m="1925660">necessary</span> <span m="1926320">to</span> <span m="1926520">first</span> <span m="1927200">put</span> <span m="1927360">on</span> <span m="1927450">my</span> <span m="1927600">underwear</span> <span m="1928130">or</span> <span m="1928270">first</span> <span m="1928550">put</span> <span m="1928670">on</span> <span m="1928780">my</span> <span m="1928880">shirt.</span> <span m="1929190">I</span> <span m="1929250">can</span> <span m="1929380">do</span> <span m="1929490">either</span> <span m="1930040">of</span> <span m="1930170">the</span> <span m="1930300">two.</span> </p>
<p><span m="1930860">So</span> <span m="1931670">we're</span> <span m="1931790">getting</span> <span m="1932120">sort</span> <span m="1932420">of</span> <span m="1932720">the</span> <span m="1934360">I</span> <span m="1934440">don't</span> <span m="1934650">care</span> <span m="1934820">so</span> <span m="1934990">much.</span> <span m="1935780">I</span> <span m="1935850">want</span> <span m="1935980">to</span> <span m="1936070">put</span> <span m="1936250">on</span> <span m="1936400">a</span> <span m="1936520">tie,</span> <span m="1938340">put</span> <span m="1938550">on</span> <span m="1938690">a</span> <span m="1938760">jacket</span> <span m="1939120">as</span> <span m="1939300">well,</span> <span m="1942800">and</span> <span m="1947040">after</span> <span m="1947230">the</span> <span m="1947365">pants,</span> <span m="1947500">I</span> <span m="1947530">need</span> <span m="1947710">to</span> <span m="1947790">put</span> <span m="1947960">on</span> <span m="1948100">my</span> <span m="1948260">belt,</span> <span m="1950240">but</span> <span m="1951970">I</span> <span m="1952040">like</span> <span m="1952260">to</span> <span m="1952370">finish</span> <span m="1952740">all</span> <span m="1952880">that</span> <span m="1953090">before</span> <span m="1953410">I</span> <span m="1953440">put</span> <span m="1953650">on</span> <span m="1953760">my</span> <span m="1953870">jacket.</span> <span m="1955590">And</span> <span m="1956380">I</span> <span m="1956540">also</span> <span m="1956820">have</span> <span m="1957110">my</span> <span m="1958640">right</span> <span m="1958990">sock</span> <span m="1960350">that</span> <span m="1960530">I</span> <span m="1960560">like</span> <span m="1960760">to</span> <span m="1960870">put</span> <span m="1961100">on</span> <span m="1962580">and</span> <span m="1965630">I</span> <span m="1965750">need</span> <span m="1965900">to</span> <span m="1965970">do</span> <span m="1966070">this</span> <span m="1966340">first</span> <span m="1966740">before</span> <span m="1967050">I</span> <span m="1967090">put</span> <span m="1967270">on</span> <span m="1967370">my</span> <span m="1967500">right</span> <span m="1967750">shoe.</span> <span m="1969042">That</span> <span m="1969490">makes</span> <span m="1969750">sense.</span> <span m="1973980">And</span> <span m="1974830">I</span> <span m="1975560">definitely</span> <span m="1976030">like</span> <span m="1976220">to</span> <span m="1976340">finish</span> <span m="1976830">putting</span> <span m="1976980">on</span> <span m="1977150">my</span> <span m="1977270">pants</span> <span m="1977650">before</span> <span m="1978160">I</span> <span m="1978200">put</span> <span m="1978430">on</span> <span m="1978550">my</span> <span m="1978680">shoes.</span> <span m="1979380">So</span> <span m="1979670">let's</span> <span m="1981050">have</span> <span m="1982140">a</span> <span m="1982340">preference</span> <span m="1982980">relationship</span> <span m="1983730">over</span> <span m="1983980">here</span> <span m="1984200">as</span> <span m="1984340">well.</span> </p>
<p><span m="1985280">But</span> <span m="1986110">I</span> <span m="1986270">do</span> <span m="1986420">not</span> <span m="1986590">really</span> <span m="1986900">care,</span> <span m="1987140">actually.</span> <span m="1987420">I</span> <span m="1987470">can</span> <span m="1987650">put</span> <span m="1987800">on</span> <span m="1987910">my</span> <span m="1988110">socks</span> <span m="1988870">first</span> <span m="1990800">and</span> <span m="1991060">then</span> <span m="1991290">my</span> <span m="1991440">underwear</span> <span m="1991930">and</span> <span m="1992020">then</span> <span m="1992140">my</span> <span m="1992270">shirt.</span> <span m="1992890">I</span> <span m="1993000">don't</span> <span m="1993220">mind</span> <span m="1993440">so</span> <span m="1993630">much.</span> <span m="1994780">I</span> <span m="1994950">also</span> <span m="1995180">have</span> <span m="1995400">my</span> <span m="1995520">left</span> <span m="1996470">sock</span> <span m="1999900">and</span> <span m="2000220">my</span> <span m="2000410">left</span> <span m="2001960">shoe.</span> <span m="2005360">And</span> <span m="2005550">again,</span> <span m="2006580">I</span> <span m="2006800">like</span> <span m="2007160">this</span> <span m="2010610">to</span> <span m="2010770">be</span> <span m="2010940">preceded</span> <span m="2011530">by</span> <span m="2011650">putting</span> <span m="2011900">on</span> <span m="2012010">my</span> <span m="2012140">pants.</span> <span m="2013270">So</span> <span m="2013430">this</span> <span m="2013630">could</span> <span m="2013790">be</span> <span m="2014270">a</span> <span m="2014480">relation,</span> <span m="2015380">a</span> <span m="2015500">sort</span> <span m="2015740">of</span> <span m="2015860">a</span> <span m="2015910">description</span> <span m="2016410">of</span> <span m="2016530">a</span> <span m="2016580">partial</span> <span m="2017020">order.</span> </p>
<p><span m="2019690">Well,</span> <span m="2020450">because</span> <span m="2021040">it's</span> <span m="2021100">a</span> <span m="2021290">Hesse</span> <span m="2021380">diagram,</span> <span m="2022290">so</span> <span m="2022390">let's</span> <span m="2022560">talk</span> <span m="2022750">about</span> <span m="2023010">it</span> <span m="2023150">a</span> <span m="2023200">little</span> <span m="2023410">bit</span> <span m="2025370">and</span> <span m="2025550">then</span> <span m="2025690">I</span> <span m="2025730">will</span> <span m="2025850">define</span> <span m="2027080">what</span> <span m="2028090">the</span> <span m="2028180">official</span> <span m="2028600">definition</span> <span m="2029180">of</span> <span m="2029850">this</span> <span m="2030010">is.</span> <span m="2032150">So</span> <span m="2032330">let's</span> <span m="2032530">first</span> <span m="2032790">look</span> <span m="2032980">at</span> <span m="2033060">this.</span> <span m="2033450">So</span> <span m="2033600">this</span> <span m="2033800">is</span> <span m="2033930">a</span> <span m="2033990">partial</span> <span m="2034430">order.</span> <span m="2036440">It</span> <span m="2037110">means</span> <span m="2037430">[? a ?]</span> <span m="2037510">percent</span> <span m="2038480">of</span> <span m="2038600">partial</span> <span m="2038980">order,</span> <span m="2039160">so</span> <span m="2040010">it's</span> <span m="2040270">reflexive.</span> <span m="2047676">The</span> <span m="2048120">pants</span> <span m="2048500">are</span> <span m="2048659">related</span> <span m="2049060">to</span> <span m="2049210">themselves,</span> <span m="2050560">so</span> <span m="2051020">I</span> <span m="2051130">put</span> <span m="2051370">them</span> <span m="2051540">on.</span> <span m="2056409">Before</span> <span m="2056659">I</span> <span m="2056699">put</span> <span m="2056860">on</span> <span m="2057080">the</span> <span m="2057290">pants,</span> <span m="2057370">I</span> <span m="2057389">need</span> <span m="2057550">to</span> <span m="2057610">put</span> <span m="2057780">on</span> <span m="2057889">the</span> <span m="2058010">underwear,</span> <span m="2058550">but</span> <span m="2058980">if</span> <span m="2059199">I</span> <span m="2060300">need</span> <span m="2060530">to</span> <span m="2060639">put</span> <span m="2060850">on</span> <span m="2061010">my</span> <span m="2061150">belt</span> <span m="2062190">after</span> <span m="2062610">I</span> <span m="2062670">put</span> <span m="2062850">on</span> <span m="2062960">my</span> <span m="2063080">underwear,</span> <span m="2063610">then</span> <span m="2063810">also</span> <span m="2065090">I</span> <span m="2065210">notice</span> <span m="2065600">I</span> <span m="2065730">first</span> <span m="2066159">need</span> <span m="2066260">to</span> <span m="2066320">put</span> <span m="2066469">on</span> <span m="2066550">my</span> <span m="2066699">underwear</span> <span m="2067159">before</span> <span m="2067600">I</span> <span m="2067659">put</span> <span m="2067850">on</span> <span m="2067960">my</span> <span m="2068090">belt.</span> </p>
<p><span m="2068989">So</span> <span m="2069510">you</span> <span m="2069710">have</span> <span m="2069840">transitivity</span> <span m="2070929">in</span> <span m="2072750">this</span> <span m="2072909">example.</span> <span m="2077520">It's</span> <span m="2077730">also</span> <span m="2079370">the</span> <span m="2079510">other</span> <span m="2079750">property</span> <span m="2080140">is</span> <span m="2080530">that</span> <span m="2080800">it</span> <span m="2081070">is</span> <span m="2081659">antisymmetric.</span> <span m="2083610">It's</span> <span m="2083810">not</span> <span m="2084020">true</span> <span m="2084409">that</span> <span m="2084949">I</span> <span m="2085070">can</span> <span m="2085290">first</span> <span m="2085610">put</span> <span m="2085739">on</span> <span m="2085850">my</span> <span m="2085960">right</span> <span m="2086260">shoe</span> <span m="2086560">and</span> <span m="2086810">then</span> <span m="2086980">my</span> <span m="2087139">right</span> <span m="2087429">sock,</span> <span m="2089570">so</span> <span m="2090530">we</span> <span m="2090699">only</span> <span m="2090969">have</span> <span m="2091810">one</span> <span m="2092120">direction</span> <span m="2092600">over</span> <span m="2092889">here.</span> <span m="2094409">Now,</span> <span m="2095040">I</span> <span m="2095120">did</span> <span m="2095250">not</span> <span m="2095449">put</span> <span m="2095610">in</span> <span m="2095850">all</span> <span m="2096100">the</span> <span m="2096260">edges</span> <span m="2096659">that</span> <span m="2096750">are</span> <span m="2096900">possible</span> <span m="2097540">for</span> <span m="2097800">this</span> <span m="2097980">partial</span> <span m="2098370">order</span> <span m="2098730">because</span> <span m="2099410">if</span> <span m="2099620">I</span> <span m="2099690">really</span> <span m="2100000">want</span> <span m="2100190">to</span> <span m="2100290">continue</span> <span m="2100800">this,</span> <span m="2102080">if</span> <span m="2102350">I</span> <span m="2102420">really</span> <span m="2102660">want</span> <span m="2102830">to</span> <span m="2104340">create</span> <span m="2104740">the</span> <span m="2105200">complete</span> <span m="2105740">directed</span> <span m="2106210">graph</span> <span m="2106660">that</span> <span m="2106750">I</span> <span m="2106840">talked</span> <span m="2107110">about</span> <span m="2107400">over</span> <span m="2107700">here--</span> <span m="2110480">I</span> <span m="2110570">think</span> <span m="2110890">it</span> <span m="2111020">talks</span> <span m="2111320">about</span> <span m="2111560">it</span> <span m="2111895">somewhere--</span> <span m="2113390">over</span> <span m="2113690">here,</span> <span m="2113940">I</span> <span m="2114740">can</span> <span m="2114900">create</span> <span m="2115180">a</span> <span m="2115210">directed</span> <span m="2115660">graph</span> <span m="2116340">that</span> <span m="2116670">has</span> <span m="2116820">its</span> <span m="2117020">vertex</span> <span m="2117430">set</span> <span m="2117950">A,</span> <span m="2118310">which</span> <span m="2118470">are</span> <span m="2118570">all</span> <span m="2118740">the</span> <span m="2118900">items</span> <span m="2119350">that</span> <span m="2119415">I</span> <span m="2119480">want</span> <span m="2119610">to</span> <span m="2119690">put</span> <span m="2119880">on.</span> <span m="2120490">And</span> <span m="2121510">in</span> <span m="2121620">that</span> <span m="2121810">set</span> <span m="2123000">that</span> <span m="2125090">has</span> <span m="2125520">all</span> <span m="2125980">the</span> <span m="2126090">different</span> <span m="2127180">relationships.</span> </p>
<p><span m="2128800">Now,</span> <span m="2128930">this</span> <span m="2129110">is</span> <span m="2129240">only</span> <span m="2129455">an</span> <span m="2129670">abbreviated</span> <span m="2130360">form.</span> <span m="2130620">This</span> <span m="2130750">is</span> <span m="2130880">a</span> <span m="2131150">Hesse</span> <span m="2131240">diagram,</span> <span m="2131700">but</span> <span m="2131910">if</span> <span m="2132010">I</span> <span m="2132080">would</span> <span m="2132220">look</span> <span m="2132400">at</span> <span m="2132500">a</span> <span m="2132660">directed</span> <span m="2133570">graph,</span> <span m="2133920">then</span> <span m="2134030">I</span> <span m="2134070">would</span> <span m="2134270">need</span> <span m="2134440">to</span> <span m="2134560">look</span> <span m="2134740">at</span> <span m="2134820">the</span> <span m="2134930">closure</span> <span m="2135440">of</span> <span m="2135550">this</span> <span m="2135710">whole</span> <span m="2135930">thing.</span> <span m="2136260">That's</span> <span m="2136780">how</span> <span m="2136910">I</span> <span m="2136980">would</span> <span m="2137180">call</span> <span m="2137530">it.</span> <span m="2139500">And</span> <span m="2140710">I</span> <span m="2140910">know</span> <span m="2141210">that,</span> <span m="2141860">for</span> <span m="2142070">example,</span> <span m="2143450">this</span> <span m="2143690">underwear,</span> <span m="2144610">by</span> <span m="2144830">transitivity,</span> <span m="2145830">is</span> <span m="2146010">also</span> <span m="2146620">less</span> <span m="2147000">than</span> <span m="2147210">or</span> <span m="2147340">equal</span> <span m="2147640">than</span> <span m="2147930">or</span> <span m="2148150">related</span> <span m="2148650">to</span> <span m="2149090">the</span> <span m="2149190">belt.</span> </p>
<p><span m="2150010">So</span> <span m="2150800">in</span> <span m="2151190">a</span> <span m="2152370">full</span> <span m="2152870">graph,</span> <span m="2153680">I</span> <span m="2160320">would</span> <span m="2160500">have</span> <span m="2161670">another</span> <span m="2162020">edge</span> <span m="2162220">over</span> <span m="2162600">here.</span> <span m="2164240">And</span> <span m="2164750">in</span> <span m="2164850">a</span> <span m="2164950">same</span> <span m="2165300">way,</span> <span m="2165870">I</span> <span m="2166020">would</span> <span m="2166230">have</span> <span m="2166460">an</span> <span m="2166620">edge</span> <span m="2167520">from</span> <span m="2167790">here</span> <span m="2168320">to</span> <span m="2168530">here.</span> <span m="2169570">I</span> <span m="2169620">would</span> <span m="2169800">have</span> <span m="2169930">an</span> <span m="2170070">edge</span> <span m="2170460">over</span> <span m="2170800">here</span> <span m="2171910">by</span> <span m="2172130">transitivity.</span> <span m="2173510">Also</span> <span m="2174240">I</span> <span m="2174360">can</span> <span m="2174550">see</span> <span m="2174760">that</span> <span m="2174825">the</span> <span m="2174890">shirt</span> <span m="2175480">goes</span> <span m="2175730">before</span> <span m="2176080">the</span> <span m="2176320">pants,</span> <span m="2176560">before</span> <span m="2176870">the</span> <span m="2176980">right</span> <span m="2177280">shoe,</span> <span m="2178090">so</span> <span m="2178410">the</span> <span m="2178510">shirt</span> <span m="2178840">is</span> <span m="2179050">also</span> <span m="2179510">related</span> <span m="2181850">all</span> <span m="2182090">the</span> <span m="2182200">way</span> <span m="2183160">to</span> <span m="2183300">the</span> <span m="2183430">right</span> <span m="2183680">shoe</span> <span m="2184190">and</span> <span m="2184350">similarly</span> <span m="2184790">to</span> <span m="2184940">the</span> <span m="2185050">left</span> <span m="2185290">shoe.</span> </p>
<p><span m="2186210">I</span> <span m="2186370">also</span> <span m="2186670">have</span> <span m="2186940">that</span> <span m="2187075">I</span> <span m="2187210">have</span> <span m="2187900">self</span> <span m="2188360">loops</span> <span m="2188630">in</span> <span m="2188760">here,</span> <span m="2190260">like</span> <span m="2190710">a</span> <span m="2190890">tie</span> <span m="2191320">is</span> <span m="2191470">related</span> <span m="2191810">to</span> <span m="2191920">itself,</span> <span m="2193110">a</span> <span m="2193550">jacket</span> <span m="2193930">as</span> <span m="2194120">well,</span> <span m="2194670">and</span> <span m="2194850">so</span> <span m="2194990">forth.</span> <span m="2195440">So</span> <span m="2195540">I</span> <span m="2195640">can</span> <span m="2195720">put</span> <span m="2195870">in</span> <span m="2196020">all</span> <span m="2196270">these</span> <span m="2196450">extra</span> <span m="2196830">edges</span> <span m="2197180">and</span> <span m="2197410">as</span> <span m="2197500">you</span> <span m="2197650">can</span> <span m="2197820">see,</span> <span m="2201800">this</span> <span m="2201920">will</span> <span m="2202000">be</span> <span m="2202110">quite</span> <span m="2202340">a</span> <span m="2202390">mess,</span> <span m="2203500">so</span> <span m="2203640">the</span> <span m="2203930">Hesse</span> <span m="2203970">diagram</span> <span m="2204380">is</span> <span m="2204510">a</span> <span m="2204560">much</span> <span m="2204800">nicer,</span> <span m="2205090">official</span> <span m="2205490">interpretation</span> <span m="2207440">of</span> <span m="2207790">what's</span> <span m="2208020">going</span> <span m="2208340">on.</span> </p>
<p><span m="2209430">So</span> <span m="2210390">let's</span> <span m="2210650">define</span> <span m="2211410">what</span> <span m="2211770">this</span> <span m="2211990">really</span> <span m="2212470">is</span> <span m="2215760">and</span> <span m="2220500">then</span> <span m="2220600">we'll</span> <span m="2220890">continue</span> <span m="2221180">with</span> <span m="2221490">some</span> <span m="2221750">nice</span> <span m="2222270">properties</span> <span m="2223220">of</span> <span m="2223870">this</span> <span m="2224050">structure.</span> <span m="2233890">So</span> <span m="2234250">what</span> <span m="2234490">is</span> <span m="2234700">a</span> <span m="2234755">Hesse</span> <span m="2234810">diagram?</span> <span m="2236430">A</span> <span m="2236540">Hesse</span> <span m="2236960">diagram</span> <span m="2237430">is</span> <span m="2237660">really</span> <span m="2238730">one</span> <span m="2239380">in</span> <span m="2239600">which</span> <span m="2243250">I</span> <span m="2243350">use</span> <span m="2248800">the</span> <span m="2248890">set</span> <span m="2249290">A</span> <span m="2249780">as</span> <span m="2249980">the</span> <span m="2250060">vertices.</span> <span m="2253240">So</span> <span m="2253500">it</span> <span m="2253560">is</span> <span m="2253740">a</span> <span m="2253790">directed</span> <span m="2254300">graph--</span> <span m="2256040">a</span> <span m="2256180">different</span> <span m="2256480">one</span> <span m="2258330">than</span> <span m="2258460">the</span> <span m="2258610">one</span> <span m="2258686">that</span> <span m="2258763">we</span> <span m="2258840">talked</span> <span m="2259130">about</span> <span m="2259400">it</span> <span m="2259455">up</span> <span m="2259510">there.</span> <span m="2260000">So</span> <span m="2260170">it's</span> <span m="2260340">a</span> <span m="2260390">directed</span> <span m="2260880">graph</span> <span m="2262830">in</span> <span m="2263030">which</span> <span m="2264440">we</span> <span m="2268420">have</span> <span m="2268620">the</span> <span m="2268710">vertex</span> <span m="2268980">set</span> <span m="2269250">A,</span> <span m="2272600">but</span> <span m="2272750">the</span> <span m="2272930">edge</span> <span m="2273170">set</span> <span m="2273370">is</span> <span m="2273610">a</span> <span m="2273650">little</span> <span m="2273820">bit</span> <span m="2273950">different.</span> </p>
<p><span m="2275350">So</span> <span m="2275760">it</span> <span m="2275930">is</span> <span m="2276110">the</span> <span m="2276185">edge</span> <span m="2276260">set</span> <span m="2278970">that</span> <span m="2279700">corresponds</span> <span m="2280230">to</span> <span m="2280340">this,</span> <span m="2281190">but</span> <span m="2281350">they</span> <span m="2281460">subtract</span> <span m="2282490">a</span> <span m="2282590">whole</span> <span m="2282880">bunch.</span> <span m="2284230">First</span> <span m="2284510">of</span> <span m="2284570">all,</span> <span m="2285010">we</span> <span m="2285420">remove</span> <span m="2285970">all</span> <span m="2286170">the</span> <span m="2286240">self</span> <span m="2286640">loops</span> <span m="2287660">that</span> <span m="2287880">we</span> <span m="2287930">have,</span> <span m="2289330">so</span> <span m="2290710">minus</span> <span m="2291210">all</span> <span m="2292160">the</span> <span m="2292260">self</span> <span m="2292640">loops</span> <span m="2294780">and</span> <span m="2296230">we</span> <span m="2296420">also</span> <span m="2296750">take</span> <span m="2297070">out</span> <span m="2299250">all</span> <span m="2299480">the</span> <span m="2299640">edges</span> <span m="2302540">that</span> <span m="2302790">are</span> <span m="2303040">implied</span> <span m="2303450">by</span> <span m="2303720">transitivity.</span> <span m="2314860">So</span> <span m="2315040">that's</span> <span m="2315150">a</span> <span m="2315260">definition</span> <span m="2315760">of</span> <span m="2315890">a</span> <span m="2316190">Hesse</span> <span m="2316240">diagram.</span> </p>
<p><span m="2319910">Now,</span> <span m="2320070">when</span> <span m="2320180">we</span> <span m="2320320">look</span> <span m="2320540">at</span> <span m="2320630">the</span> <span m="2320710">Hesse</span> <span m="2321020">diagram</span> <span m="2321530">over</span> <span m="2321790">here,</span> <span m="2328100">so</span> <span m="2328290">let</span> <span m="2328400">me</span> <span m="2328520">take</span> <span m="2328840">out</span> <span m="2329060">these</span> <span m="2329650">nodes</span> <span m="2330080">again</span> <span m="2330335">or</span> <span m="2330590">these</span> <span m="2331170">edges.</span> <span m="2339650">So</span> <span m="2340610">looking</span> <span m="2340930">at</span> <span m="2340980">this</span> <span m="2341150">Hesse</span> <span m="2341450">diagram,</span> <span m="2342440">you</span> <span m="2342570">really</span> <span m="2342820">see</span> <span m="2343050">a</span> <span m="2343080">nice</span> <span m="2343410">structure</span> <span m="2343730">in</span> <span m="2344050">there.</span> <span m="2344920">It</span> <span m="2345110">seems</span> <span m="2345460">like</span> <span m="2346040">we</span> <span m="2346150">can</span> <span m="2346330">talk</span> <span m="2346630">about</span> <span m="2347380">smallest</span> <span m="2347920">elements</span> <span m="2348520">like</span> <span m="2349350">a</span> <span m="2349480">shirt,</span> <span m="2349880">just</span> <span m="2350130">like</span> <span m="2350830">a</span> <span m="2350940">small</span> <span m="2351550">element.</span> <span m="2352000">It's</span> <span m="2352120">sort</span> <span m="2352420">of</span> <span m="2353570">less</span> <span m="2353880">than</span> <span m="2354020">or</span> <span m="2354110">equal</span> <span m="2354490">to</span> <span m="2354720">if</span> <span m="2354860">you</span> <span m="2354990">think</span> <span m="2355250">about</span> <span m="2355490">this</span> <span m="2356090">as</span> <span m="2356270">being</span> <span m="2356660">the</span> <span m="2357140">3%,</span> <span m="2357950">then</span> <span m="2358100">the</span> <span m="2358360">tie</span> <span m="2358620">and</span> <span m="2358730">the</span> <span m="2358985">jacket</span> <span m="2359240">and</span> <span m="2359675">the</span> <span m="2359783">pants</span> <span m="2359892">and</span> <span m="2360001">the</span> <span m="2360110">right</span> <span m="2360390">shoe</span> <span m="2361190">and</span> <span m="2361380">so</span> <span m="2361590">on.</span> <span m="2362260">So</span> <span m="2363120">you</span> <span m="2363280">can</span> <span m="2363430">see</span> <span m="2363890">a</span> <span m="2363920">clear</span> <span m="2364240">order</span> <span m="2364750">in</span> <span m="2364860">this</span> <span m="2365010">particular</span> <span m="2365420">graph.</span> </p>
<p><span m="2370510">So</span> <span m="2370730">let's</span> <span m="2373060">have</span> <span m="2373210">a</span> <span m="2373290">look</span> <span m="2373480">at</span> <span m="2373570">this.</span> <span m="2375470">When</span> <span m="2375630">I</span> <span m="2375650">look</span> <span m="2375860">at</span> <span m="2375900">this</span> <span m="2376090">graph,</span> <span m="2376390">I</span> <span m="2376460">also</span> <span m="2376810">do</span> <span m="2376920">not</span> <span m="2377170">see</span> <span m="2377390">any</span> <span m="2378140">cycles.</span> <span m="2379210">I</span> <span m="2379310">do</span> <span m="2379410">not</span> <span m="2379620">see</span> <span m="2380650">that</span> <span m="2380840">the</span> <span m="2380930">shirt</span> <span m="2381580">is</span> <span m="2381820">less</span> <span m="2381886">than</span> <span m="2381953">or</span> <span m="2382020">equal</span> <span m="2382240">to</span> <span m="2382340">the</span> <span m="2382530">pants.</span> <span m="2383180">It's</span> <span m="2383350">related</span> <span m="2383670">to</span> <span m="2383770">the</span> <span m="2383860">right</span> <span m="2384090">shoe</span> <span m="2384350">and</span> <span m="2384450">then</span> <span m="2384550">it's</span> <span m="2384670">related</span> <span m="2384990">to</span> <span m="2385090">itself</span> <span m="2385510">again,</span> <span m="2385990">so</span> <span m="2386360">I</span> <span m="2386460">do</span> <span m="2386570">not</span> <span m="2386740">see</span> <span m="2386880">any</span> <span m="2387040">cycles.</span> <span m="2388210">And</span> <span m="2388340">this</span> <span m="2388480">turns</span> <span m="2388770">out</span> <span m="2388960">to</span> <span m="2389030">be</span> <span m="2389160">general</span> <span m="2389510">property</span> <span m="2390150">of</span> <span m="2390880">posets</span> <span m="2392260">and</span> <span m="2392460">that's</span> <span m="2392690">what</span> <span m="2392900">we</span> <span m="2393053">are</span> <span m="2393206">going</span> <span m="2393360">to</span> <span m="2393525">prove</span> <span m="2393690">next.</span> </p>
<p><span m="2397020">So</span> <span m="2399290">let's</span> <span m="2399740">do</span> <span m="2399940">that</span> <span m="2401610">over</span> <span m="2401940">here.</span> <span m="2414600">So</span> <span m="2414940">you</span> <span m="2415150">see</span> <span m="2415480">that</span> <span m="2417440">there</span> <span m="2417580">are</span> <span m="2417610">no</span> <span m="2417860">cycles</span> <span m="2419470">and</span> <span m="2419660">it's</span> <span m="2419800">a</span> <span m="2419850">general</span> <span m="2420140">property.</span> <span m="2420850">So</span> <span m="2421080">the</span> <span m="2421200">theorem</span> <span m="2421510">is</span> <span m="2424840">that</span> <span m="2425000">a</span> <span m="2425275">poset</span> <span m="2428640">has</span> <span m="2429650">no</span> <span m="2434790">directed</span> <span m="2435300">cycles</span> <span m="2439880">other</span> <span m="2440140">than</span> <span m="2444380">self</span> <span m="2444800">loops.</span> <span m="2452260">Now,</span> <span m="2452460">notice</span> <span m="2452600">that</span> <span m="2452740">this</span> <span m="2452940">property</span> <span m="2453200">is</span> <span m="2453460">really</span> <span m="2453660">necessary</span> <span m="2454400">to</span> <span m="2454610">have</span> <span m="2454820">a</span> <span m="2454890">proper</span> <span m="2455620">representation</span> <span m="2456450">by</span> <span m="2456550">using</span> <span m="2456930">a</span> <span m="2457220">Hesse</span> <span m="2457280">diagram</span> <span m="2458360">because</span> <span m="2458720">otherwise,</span> <span m="2459790">if</span> <span m="2459950">you</span> <span m="2460040">have</span> <span m="2460160">a</span> <span m="2460300">big,</span> <span m="2461730">directed</span> <span m="2462550">cycle,</span> <span m="2463580">then</span> <span m="2467480">only</span> <span m="2467740">one</span> <span m="2467940">of</span> <span m="2468060">those</span> <span m="2468310">edges</span> <span m="2468840">would</span> <span m="2469020">be</span> <span m="2469160">part</span> <span m="2469370">of</span> <span m="2469470">the</span> <span m="2469750">Hesse</span> <span m="2469790">diagram</span> <span m="2470260">and</span> <span m="2470370">all</span> <span m="2470450">the</span> <span m="2470580">others</span> <span m="2470850">are</span> <span m="2471000">implied</span> <span m="2471450">by</span> <span m="2471590">transitivity</span> <span m="2472350">sort</span> <span m="2472700">of.</span> <span m="2473920">And</span> <span m="2474190">that</span> <span m="2474350">is</span> <span m="2474930">getting</span> <span m="2475180">a</span> <span m="2475220">little</span> <span m="2475330">bit</span> <span m="2475470">messy</span> <span m="2476060">because</span> <span m="2476340">then</span> <span m="2476470">we</span> <span m="2476550">do</span> <span m="2476650">not</span> <span m="2476840">really</span> <span m="2477006">have</span> <span m="2477173">a</span> <span m="2477340">unique</span> <span m="2477640">representation.</span> </p>
<p><span m="2479810">But</span> <span m="2480340">luckily,</span> <span m="2480930">there</span> <span m="2481060">are</span> <span m="2481090">no</span> <span m="2481310">directed</span> <span m="2481740">cycles.</span> <span m="2482560">So</span> <span m="2482630">how</span> <span m="2482720">do</span> <span m="2482790">we</span> <span m="2482900">prove</span> <span m="2483170">this?</span> <span m="2485465">Well,</span> <span m="2485940">let's</span> <span m="2488500">do</span> <span m="2488590">this</span> <span m="2488820">by</span> <span m="2489010">contradiction</span> <span m="2492350">and</span> <span m="2492860">see</span> <span m="2495450">what</span> <span m="2495770">happens.</span> <span m="2497560">So</span> <span m="2497760">suppose</span> <span m="2498200">the</span> <span m="2498300">contrary.</span> <span m="2500460">So</span> <span m="2500690">suppose</span> <span m="2502680">that</span> <span m="2502960">actually</span> <span m="2504000">there</span> <span m="2504200">exists</span> <span m="2505770">at</span> <span m="2505920">least</span> <span m="2506270">two,</span> <span m="2506640">an</span> <span m="2506930">integer,</span> <span m="2507090">at</span> <span m="2507200">least</span> <span m="2507500">two,</span> <span m="2508810">so</span> <span m="2509010">at</span> <span m="2509130">least</span> <span m="2509530">n</span> <span m="2509850">distinct</span> <span m="2511280">elements,</span> <span m="2516330">a1</span> <span m="2517100">all</span> <span m="2517380">the</span> <span m="2517470">way</span> <span m="2517700">up</span> <span m="2517880">to</span> <span m="2518100">an</span> <span m="2518940">that</span> <span m="2519060">form</span> <span m="2519220">a</span> <span m="2519380">cycle,</span> <span m="2520310">so</span> <span m="2520770">such</span> <span m="2521340">that</span> <span m="2535710">you</span> <span m="2535940">have</span> <span m="2536130">a</span> <span m="2536270">directed</span> <span m="2536320">cycle.</span> <span m="2538720">So</span> <span m="2539050">we</span> <span m="2539190">would</span> <span m="2540210">put</span> <span m="2540420">it</span> <span m="2540630">in</span> <span m="2540800">formula</span> <span m="2541630">like</span> <span m="2541820">this.</span> <span m="2543220">a1</span> <span m="2544040">is</span> <span m="2544290">related</span> <span m="2544790">to</span> <span m="2545960">a2</span> <span m="2547700">to</span> <span m="2548570">a3</span> <span m="2550100">and</span> <span m="2550290">so</span> <span m="2550510">on</span> <span m="2551150">all</span> <span m="2551350">the</span> <span m="2551430">way</span> <span m="2551650">up</span> <span m="2551790">to</span> <span m="2552740">an</span> <span m="2553470">minus</span> <span m="2553860">1</span> <span m="2555600">an.</span> <span m="2556643">And</span> <span m="2557350">we</span> <span m="2558070">have</span> <span m="2558220">a</span> <span m="2558270">cycle,</span> <span m="2559330">so</span> <span m="2559620">this</span> <span m="2559830">goes</span> <span m="2560070">back</span> <span m="2560390">to</span> <span m="2560640">a1.</span> </p>
<p><span m="2562480">So</span> <span m="2562730">why</span> <span m="2562920">would</span> <span m="2563070">this</span> <span m="2563270">be</span> <span m="2563410">a</span> <span m="2563460">contradiction?</span> <span m="2564560">So</span> <span m="2565380">maybe</span> <span m="2565590">you</span> <span m="2565690">can</span> <span m="2565820">help</span> <span m="2566040">me</span> <span m="2566160">out</span> <span m="2566330">here.</span> <span m="2567920">So</span> <span m="2569740">what</span> <span m="2569930">can</span> <span m="2570150">I</span> <span m="2570670">already</span> <span m="2570910">derive</span> <span m="2571320">from</span> <span m="2571490">those</span> <span m="2571720">properties</span> <span m="2572150">that</span> <span m="2572290">I</span> <span m="2572430">have</span> <span m="2572730">over</span> <span m="2572980">here?</span> <span m="2573140">So</span> <span m="2573260">I</span> <span m="2573350">know</span> <span m="2573495">that</span> <span m="2573640">the</span> <span m="2573730">partial</span> <span m="2574170">order</span> <span m="2575120">is</span> <span m="2575360">antisymmetric,</span> <span m="2578400">it</span> <span m="2578750">is</span> <span m="2578970">transitive,</span> <span m="2579950">it's</span> <span m="2580160">reflexive.</span> <span m="2580970">So</span> <span m="2582000">how</span> <span m="2584670">can</span> <span m="2584880">I</span> <span m="2585040">get</span> <span m="2585280">to</span> <span m="2585370">a</span> <span m="2585800">contradiction</span> <span m="2586145">here?</span> <span m="2587970">So</span> <span m="2588160">let's</span> <span m="2588350">think</span> <span m="2588540">about</span> <span m="2588810">it</span> <span m="2588940">a</span> <span m="2588970">little</span> <span m="2589200">bit.</span> </p>
<p><span m="2593770">Is</span> <span m="2593860">it</span> <span m="2594030">possible,</span> <span m="2594480">for</span> <span m="2594640">example,</span> <span m="2595110">that</span> <span m="2595380">we</span> <span m="2595780">could</span> <span m="2596020">violate</span> <span m="2596790">the</span> <span m="2597140">antisymmetry</span> <span m="2598330">of</span> <span m="2600040">the</span> <span m="2601690">poset?</span> <span m="2603460">So</span> <span m="2603670">can</span> <span m="2603800">we</span> <span m="2603940">find</span> <span m="2604290">maybe</span> <span m="2604670">two</span> <span m="2605470">distinct</span> <span m="2605980">elements</span> <span m="2606980">such</span> <span m="2607340">that</span> <span m="2607720">say</span> <span m="2608000">x</span> <span m="2608620">is</span> <span m="2608840">related</span> <span m="2609150">to</span> <span m="2609290">y</span> <span m="2609780">and</span> <span m="2609896">y</span> <span m="2610013">is</span> <span m="2610130">related</span> <span m="2610570">to</span> <span m="2610680">x,</span> <span m="2612780">but</span> <span m="2615110">it's</span> <span m="2615310">not</span> <span m="2615460">true</span> <span m="2615640">that</span> <span m="2615790">x</span> <span m="2616020">is</span> <span m="2616130">equal</span> <span m="2616400">to</span> <span m="2616530">y.</span> <span m="2618810">For</span> <span m="2619920">example,</span> <span m="2621140">if</span> <span m="2621360">you</span> <span m="2621430">have</span> <span m="2621580">very</span> <span m="2621810">small</span> <span m="2622130">cycle,</span> <span m="2623080">say</span> <span m="2624360">a1</span> <span m="2628080">is</span> <span m="2628320">related</span> <span m="2628690">to</span> <span m="2628990">an</span> <span m="2630190">and</span> <span m="2630360">then</span> <span m="2630610">related</span> <span m="2631020">to</span> <span m="2631210">a1,</span> <span m="2631600">again,</span> <span m="2632940">well,</span> <span m="2633090">then</span> <span m="2633280">I</span> <span m="2633360">would</span> <span m="2633540">have</span> <span m="2633775">that</span> <span m="2634010">a1</span> <span m="2634500">is</span> <span m="2634620">related</span> <span m="2634960">to</span> <span m="2635130">an</span> <span m="2635630">and</span> <span m="2636240">an</span> <span m="2636570">is</span> <span m="2636690">related</span> <span m="2637010">to</span> <span m="2637390">a1.</span> </p>
<p><span m="2639930">We</span> <span m="2640070">should</span> <span m="2640370">have</span> <span m="2640770">that</span> <span m="2641100">an</span> <span m="2641440">is</span> <span m="2641600">then</span> <span m="2641730">equal</span> <span m="2641980">to</span> <span m="2642140">a1</span> <span m="2642590">but,</span> <span m="2642700">that's</span> <span m="2642900">not</span> <span m="2643050">true</span> <span m="2644140">because</span> <span m="2645270">the</span> <span m="2645370">issue</span> <span m="2645520">of</span> <span m="2645670">distinct</span> <span m="2646120">elements</span> <span m="2646570">over</span> <span m="2646830">here.</span> <span m="2647850">So</span> <span m="2648050">that</span> <span m="2648220">seems</span> <span m="2648450">to</span> <span m="2648550">be</span> <span m="2648680">an</span> <span m="2648760">interesting</span> <span m="2649270">idea.</span> <span m="2649610">So</span> <span m="2649740">maybe</span> <span m="2650130">we</span> <span m="2650490">can</span> <span m="2653410">prove</span> <span m="2653710">something</span> <span m="2654110">of</span> <span m="2654240">that</span> <span m="2654440">type.</span> <span m="2655340">So</span> <span m="2656100">can</span> <span m="2656280">we</span> <span m="2656420">actually</span> <span m="2656750">show</span> <span m="2657140">that</span> <span m="2657330">a1</span> <span m="2658120">is</span> <span m="2659510">related</span> <span m="2660090">to</span> <span m="2660270">an?</span> <span m="2661970">We</span> <span m="2662110">can</span> <span m="2662310">write</span> <span m="2662540">what</span> <span m="2662850">kind</span> <span m="2662870">of</span> <span m="2662890">a</span> <span m="2662910">property</span> <span m="2663400">of</span> <span m="2663510">a</span> <span m="2663570">poset</span> <span m="2664040">do</span> <span m="2664150">we</span> <span m="2664280">use</span> <span m="2664540">here</span> <span m="2665230">to</span> <span m="2665370">make</span> <span m="2665530">that</span> <span m="2665660">happen?</span> </p>
<p><span m="2669920">I</span> <span m="2670060">heard</span> <span m="2670280">something</span> <span m="2670740">vaguely,</span> <span m="2672704">a</span> <span m="2673195">mumble.</span> <span m="2675650">Yeah,</span> <span m="2676050">the</span> <span m="2676250">transitive</span> <span m="2676400">property.</span> <span m="2677600">So</span> <span m="2677660">how</span> <span m="2677780">do</span> <span m="2677870">we</span> <span m="2677970">do</span> <span m="2678130">it?</span> <span m="2678840">Well,</span> <span m="2679200">we</span> <span m="2679450">take</span> <span m="2679710">those</span> <span m="2680010">three</span> <span m="2680210">together</span> <span m="2680790">and</span> <span m="2681050">we</span> <span m="2681230">conclude</span> <span m="2682750">that</span> <span m="2682970">a1</span> <span m="2683310">is</span> <span m="2683470">also</span> <span m="2684160">related</span> <span m="2684500">to</span> <span m="2684650">a3.</span> <span m="2685630">We</span> <span m="2685720">have</span> <span m="2686000">a4</span> <span m="2686690">over</span> <span m="2687060">here,</span> <span m="2688290">so</span> <span m="2689110">together</span> <span m="2690000">with</span> <span m="2691250">this</span> <span m="2691590">one,</span> <span m="2691940">so</span> <span m="2692150">a1</span> <span m="2692280">is</span> <span m="2692460">related</span> <span m="2692710">to</span> <span m="2692820">a3</span> <span m="2693280">and</span> <span m="2693455">a3</span> <span m="2693630">is</span> <span m="2693720">related</span> <span m="2693900">to</span> <span m="2694030">a4.</span> <span m="2695420">We</span> <span m="2695570">have</span> <span m="2696010">that</span> <span m="2696230">a1</span> <span m="2696740">is</span> <span m="2696900">related</span> <span m="2697250">to</span> <span m="2697420">a4</span> <span m="2698920">and</span> <span m="2699090">you</span> <span m="2699180">can</span> <span m="2699520">use</span> <span m="2699910">induction</span> <span m="2700920">if</span> <span m="2702910">you</span> <span m="2703030">want</span> <span m="2703160">to</span> <span m="2703230">be</span> <span m="2703300">very</span> <span m="2703550">precise</span> <span m="2704050">here,</span> <span m="2704310">which</span> <span m="2704520">you</span> <span m="2704790">should,</span> <span m="2705130">actually,</span> <span m="2705560">but</span> <span m="2706200">I</span> <span m="2706340">will</span> <span m="2706460">not</span> <span m="2706650">do</span> <span m="2706780">this.</span> </p>
<p><span m="2707740">So</span> <span m="2708260">you</span> <span m="2708480">will</span> <span m="2708630">use</span> <span m="2708860">induction</span> <span m="2709170">and</span> <span m="2709480">go</span> <span m="2709640">all</span> <span m="2709900">the</span> <span m="2709990">way</span> <span m="2710160">to</span> <span m="2711160">the</span> <span m="2711260">fact</span> <span m="2711590">that</span> <span m="2711820">a1</span> <span m="2712220">is</span> <span m="2712440">actually</span> <span m="2713140">related</span> <span m="2713580">to</span> <span m="2713770">an.</span> <span m="2715110">But</span> <span m="2715230">wait</span> <span m="2715400">a</span> <span m="2715420">minute.</span> <span m="2716710">We</span> <span m="2716770">also</span> <span m="2717120">have</span> <span m="2717810">this</span> <span m="2718360">particular</span> <span m="2720030">property</span> <span m="2722560">and</span> <span m="2724000">a1</span> <span m="2724490">is</span> <span m="2724720">not</span> <span m="2724960">equal</span> <span m="2725250">to</span> <span m="2725440">an</span> <span m="2725960">by</span> <span m="2726260">our</span> <span m="2726770">assumption.</span> <span m="2728330">So</span> <span m="2728560">we</span> <span m="2728660">get</span> <span m="2728870">a</span> <span m="2728970">contradiction,</span> <span m="2731100">which</span> <span m="2731300">means</span> <span m="2731670">that</span> <span m="2733110">what</span> <span m="2733300">we</span> <span m="2733400">had</span> <span m="2733620">over</span> <span m="2733860">here</span> <span m="2734180">is</span> <span m="2734380">not</span> <span m="2734590">true.</span> <span m="2735150">So</span> <span m="2735260">actually,</span> <span m="2735590">for</span> <span m="2735750">all</span> <span m="2736050">n,</span> <span m="2737280">at</span> <span m="2737420">least</span> <span m="2737700">two,</span> <span m="2738720">n</span> <span m="2739030">distinct</span> <span m="2739420">elements</span> <span m="2740540">a1</span> <span m="2740720">up</span> <span m="2741000">to</span> <span m="2741150">an</span> <span m="2741880">that--</span> <span m="2745440">well,</span> <span m="2746370">we</span> <span m="2746510">have</span> <span m="2746630">the</span> <span m="2746720">negative</span> <span m="2747130">of</span> <span m="2747260">this,</span> <span m="2747680">so</span> <span m="2748010">there</span> <span m="2748220">is</span> <span m="2748360">no</span> <span m="2749340">cycle.</span> </p>
<p><span m="2751220">So</span> <span m="2751410">this</span> <span m="2751660">is</span> <span m="2753170">a</span> <span m="2753230">great</span> <span m="2753510">property,</span> <span m="2753990">so</span> <span m="2754160">now</span> <span m="2754770">we</span> <span m="2754910">start</span> <span m="2755280">to</span> <span m="2755390">see</span> <span m="2756140">why</span> <span m="2756800">a</span> <span m="2756930">poset</span> <span m="2757490">is</span> <span m="2757650">actually</span> <span m="2758170">called</span> <span m="2758510">a</span> <span m="2758580">partial</span> <span m="2759010">ordered,</span> <span m="2759670">right?</span> <span m="2760530">Because</span> <span m="2760740">there's</span> <span m="2760970">no</span> <span m="2761910">directed</span> <span m="2762390">cycles</span> <span m="2762870">other</span> <span m="2763060">than</span> <span m="2763250">the</span> <span m="2763340">self</span> <span m="2763710">loops,</span> <span m="2764630">so</span> <span m="2765840">we</span> <span m="2766020">sort</span> <span m="2766280">of</span> <span m="2766360">have</span> <span m="2766570">a</span> <span m="2766700">ranking</span> <span m="2767110">to</span> <span m="2767230">the</span> <span m="2767350">elements.</span> <span m="2768210">We</span> <span m="2768520">can</span> <span m="2768840">say</span> <span m="2769350">that</span> <span m="2770430">really</span> <span m="2770940">one</span> <span m="2772550">element</span> <span m="2773180">is</span> <span m="2773540">ranked</span> <span m="2773920">less</span> <span m="2774210">than</span> <span m="2774360">another.</span> <span m="2775170">So</span> <span m="2775210">this</span> <span m="2775450">one</span> <span m="2775600">is</span> <span m="2775740">ranked</span> <span m="2775940">less</span> <span m="2776220">than</span> <span m="2776400">this,</span> <span m="2776890">it's</span> <span m="2777090">ranked</span> <span m="2777360">less</span> <span m="2777640">than</span> <span m="2777810">that,</span> <span m="2778270">and</span> <span m="2778390">it</span> <span m="2778470">cannot</span> <span m="2778750">circle</span> <span m="2779120">back</span> <span m="2779340">again</span> <span m="2779650">and</span> <span m="2779740">say</span> <span m="2780070">that</span> <span m="2780165">this</span> <span m="2780260">one</span> <span m="2780360">is</span> <span m="2780830">ranked</span> <span m="2781110">less</span> <span m="2781510">than</span> <span m="2781910">this</span> <span m="2782420">because</span> <span m="2782690">they</span> <span m="2782760">don't</span> <span m="2782970">have</span> <span m="2783080">cycles,</span> <span m="2783850">so</span> <span m="2783900">that</span> <span m="2784540">makes</span> <span m="2784810">a</span> <span m="2784840">really</span> <span m="2785090">consistent</span> <span m="2785590">story.</span> </p>
<p><span m="2787520">Notice</span> <span m="2787870">that</span> <span m="2788010">this</span> <span m="2788210">was</span> <span m="2788430">different</span> <span m="2789835">when</span> <span m="2790250">we</span> <span m="2790480">talked</span> <span m="2790710">about</span> <span m="2790920">tournament</span> <span m="2791270">grass,</span> <span m="2791580">for</span> <span m="2791720">example.</span> <span m="2792470">That</span> <span m="2792530">was</span> <span m="2792660">a</span> <span m="2792870">very</span> <span m="2793080">different</span> <span m="2793470">structure</span> <span m="2794450">and</span> <span m="2794630">we</span> <span m="2794740">could</span> <span m="2794930">not</span> <span m="2795730">think</span> <span m="2796100">of</span> <span m="2796230">a</span> <span m="2796360">winner</span> <span m="2797480">in</span> <span m="2797680">there.</span> <span m="2799920">But</span> <span m="2800150">in</span> <span m="2800210">this</span> <span m="2800430">case,</span> <span m="2803090">we</span> <span m="2803280">have</span> <span m="2803510">a</span> <span m="2803550">ranking.</span> <span m="2804890">And</span> <span m="2805040">this</span> <span m="2805250">leads</span> <span m="2805510">us</span> <span m="2805690">to</span> <span m="2805910">a</span> <span m="2805960">more</span> <span m="2806700">general</span> <span m="2811820">discussion.</span> <span m="2813220">But</span> <span m="2813380">before</span> <span m="2813660">we</span> <span m="2813770">go</span> <span m="2813980">into</span> <span m="2814250">that,</span> <span m="2817110">I'd</span> <span m="2817210">like</span> <span m="2817410">to</span> <span m="2817520">write</span> <span m="2817690">down</span> <span m="2817860">a</span> <span m="2817940">conclusion</span> <span m="2818860">of</span> <span m="2819155">this</span> <span m="2819450">theorem.</span> </p>
<p><span m="2820500">So</span> <span m="2821240">after</span> <span m="2821630">deleting</span> <span m="2824650">the</span> <span m="2824740">self</span> <span m="2825150">loops</span> <span m="2830600">from</span> <span m="2830900">a</span> <span m="2830960">poset,</span> <span m="2835210">we</span> <span m="2835400">actually</span> <span m="2836800">get</span> <span m="2837260">a</span> <span m="2837980">directed</span> <span m="2838730">acyclic</span> <span m="2839450">graph.</span> <span m="2842020">And</span> <span m="2842240">that's</span> <span m="2842680">what</span> <span m="2842990">we</span> <span m="2843140">defined</span> <span m="2843580">last</span> <span m="2843950">week</span> <span m="2844460">as</span> <span m="2844510">well.</span> <span m="2845010">So</span> <span m="2845080">a</span> <span m="2845150">directed</span> <span m="2846000">acyclic</span> <span m="2846810">graph</span> <span m="2848980">and</span> <span m="2850570">we</span> <span m="2850960">abbreviate</span> <span m="2851310">this</span> <span m="2851650">as</span> <span m="2852780">D-A-G,</span> <span m="2853095">a</span> <span m="2853410">DAG.</span> <span m="2857310">So</span> <span m="2857490">that's</span> <span m="2857690">a</span> <span m="2857800">very</span> <span m="2858040">special</span> <span m="2860190">property</span> <span m="2860670">for</span> <span m="2860840">the</span> <span m="2860930">poset.</span> </p>
<p><span m="2866430">Now</span> <span m="2866710">a</span> <span m="2866840">partial</span> <span m="2867420">order</span> <span m="2868870">has</span> <span m="2869060">elements</span> <span m="2869550">that</span> <span m="2869650">cannot</span> <span m="2869950">be</span> <span m="2870090">compared,</span> <span m="2870650">for</span> <span m="2870820">example.</span> <span m="2872090">Like</span> <span m="2872380">in</span> <span m="2872460">this</span> <span m="2872710">case,</span> <span m="2873620">these</span> <span m="2873850">two</span> <span m="2875050">have</span> <span m="2875310">absolutely</span> <span m="2875860">no</span> <span m="2877200">relationship</span> <span m="2877890">with</span> <span m="2878030">one</span> <span m="2878190">another.</span> <span m="2879130">Even</span> <span m="2879490">through</span> <span m="2879800">transitivity,</span> <span m="2882430">I</span> <span m="2882540">cannot</span> <span m="2882980">conclude</span> <span m="2883460">that</span> <span m="2883850">either</span> <span m="2883900">the</span> <span m="2884030">right</span> <span m="2884310">sock</span> <span m="2884830">is</span> <span m="2885290">related</span> <span m="2886240">to</span> <span m="2887030">the</span> <span m="2887820">underwear</span> <span m="2888310">or</span> <span m="2888640">the</span> <span m="2888805">underwear</span> <span m="2888970">related</span> <span m="2889350">to</span> <span m="2889490">the</span> <span m="2889610">right</span> <span m="2889890">sock.</span> <span m="2891970">And</span> <span m="2894300">that</span> <span m="2894500">makes</span> <span m="2894730">it</span> <span m="2894840">a</span> <span m="2894900">partial</span> <span m="2895410">order.</span> <span m="2896200">It's</span> <span m="2896440">possible</span> <span m="2896850">that</span> <span m="2897000">you</span> <span m="2897070">have</span> <span m="2897210">elements,</span> <span m="2898190">pairs</span> <span m="2898620">of</span> <span m="2898710">elements,</span> <span m="2899580">that</span> <span m="2899760">are</span> <span m="2899920">incomparable.</span> </p>
<p><span m="2901480">So</span> <span m="2901660">let</span> <span m="2901990">me</span> <span m="2902130">write</span> <span m="2902350">this</span> <span m="2902550">down.</span> <span m="2910370">So</span> <span m="2915190">what</span> <span m="2915340">we</span> <span m="2915440">really</span> <span m="2915710">want</span> <span m="2915980">to</span> <span m="2916160">though,</span> <span m="2916650">is</span> <span m="2916860">that</span> <span m="2917030">we</span> <span m="2917200">have</span> <span m="2917420">some</span> <span m="2917700">kind</span> <span m="2917960">of</span> <span m="2918090">consistent</span> <span m="2918750">ranking</span> <span m="2919480">that</span> <span m="2919650">we</span> <span m="2919810">can</span> <span m="2920550">create</span> <span m="2921000">for</span> <span m="2921190">a</span> <span m="2921230">partial</span> <span m="2921690">ordered</span> <span m="2921990">set.</span> <span m="2923620">But</span> <span m="2924300">for</span> <span m="2924520">now,</span> <span m="2924920">we</span> <span m="2925090">know</span> <span m="2925255">that</span> <span m="2925420">certain</span> <span m="2925990">pairs</span> <span m="2926500">cannot</span> <span m="2926860">be</span> <span m="2926980">compared</span> <span m="2927380">to</span> <span m="2927480">one</span> <span m="2927660">another</span> <span m="2928050">and</span> <span m="2928180">we</span> <span m="2928270">would</span> <span m="2928470">like</span> <span m="2928700">to</span> <span m="2929130">achieve</span> <span m="2929500">something</span> <span m="2930710">like</span> <span m="2930900">this.</span> </p>
<p><span m="2932170">So</span> <span m="2932230">that's</span> <span m="2932430">why</span> <span m="2932590">we</span> <span m="2932670">start</span> <span m="2932920">to</span> <span m="2933020">talk</span> <span m="2933350">about</span> <span m="2935540">what</span> <span m="2935710">it</span> <span m="2935830">means</span> <span m="2936360">if</span> <span m="2936680">a</span> <span m="2936900">and</span> <span m="2937120">b</span> <span m="2937590">are</span> <span m="2937830">incomparable</span> <span m="2944050">and</span> <span m="2946540">this</span> <span m="2946870">is,</span> <span m="2947080">if</span> <span m="2947300">neither</span> <span m="2950350">a</span> <span m="2951180">is</span> <span m="2952340">related</span> <span m="2952660">to</span> <span m="2952790">b</span> <span m="2954370">nor</span> <span m="2956020">b</span> <span m="2956480">is</span> <span m="2956750">related</span> <span m="2957150">to</span> <span m="2957630">a.</span> <span m="2959880">And</span> <span m="2960280">we</span> <span m="2960410">say</span> <span m="2960760">that</span> <span m="2960840">a</span> <span m="2960920">and</span> <span m="2961260">b</span> <span m="2961730">are</span> <span m="2962400">comparable</span> <span m="2967056">well,</span> <span m="2968720">if</span> <span m="2969420">a</span> <span m="2969863">is</span> <span m="2970306">related</span> <span m="2970860">to</span> <span m="2971030">b</span> <span m="2971410">or</span> <span m="2972290">b</span> <span m="2972680">is</span> <span m="2972910">related</span> <span m="2973460">to</span> <span m="2973700">a.</span> <span m="2977100">Now</span> <span m="2977290">we</span> <span m="2977400">can</span> <span m="2977540">have</span> <span m="2977690">a</span> <span m="2977730">very</span> <span m="2977990">special</span> <span m="2978570">order</span> <span m="2978920">which</span> <span m="2979130">we</span> <span m="2979220">call</span> <span m="2979530">total</span> <span m="2980030">order.</span> <span m="2981620">In</span> <span m="2981780">a</span> <span m="2981890">total</span> <span m="2982340">order,</span> <span m="2991340">it's</span> <span m="2991610">actually</span> <span m="2992020">partial</span> <span m="2992440">order,</span> <span m="2993260">but</span> <span m="2993490">all</span> <span m="2993730">the</span> <span m="2993830">elements</span> <span m="2994260">and</span> <span m="2994350">comparable.</span> <span m="2998640">So</span> <span m="2998800">it's</span> <span m="2998940">a</span> <span m="2999411">partial</span> <span m="2999882">order</span> <span m="3002708">in</span> <span m="3003180">which</span> <span m="3003640">every</span> <span m="3004060">pair</span> <span m="3010050">of</span> <span m="3010160">elements</span> <span m="3017490">is</span> <span m="3017870">comparable.</span> </p>
<p><span m="3020730">Now,</span> <span m="3020850">maybe</span> <span m="3021080">you</span> <span m="3021170">can</span> <span m="3021290">think</span> <span m="3021820">about</span> <span m="3022310">the</span> <span m="3022440">Hesse</span> <span m="3022770">diagram</span> <span m="3023250">of</span> <span m="3023370">a</span> <span m="3023470">total</span> <span m="3023900">order.</span> <span m="3024570">What</span> <span m="3024760">would</span> <span m="3024870">it</span> <span m="3024970">look</span> <span m="3025180">like</span> <span m="3025610">if</span> <span m="3025830">we</span> <span m="3025970">have</span> <span m="3026360">that</span> <span m="3029040">all</span> <span m="3029260">the</span> <span m="3029380">elements</span> <span m="3029810">are</span> <span m="3029880">actually</span> <span m="3030160">comparable?</span> <span m="3031300">Do</span> <span m="3031530">you</span> <span m="3031570">have</span> <span m="3031610">any</span> <span m="3031650">idea</span> <span m="3032310">what</span> <span m="3033720">kind</span> <span m="3033880">of</span> <span m="3033970">a</span> <span m="3034060">graph</span> <span m="3034600">would</span> <span m="3034780">that</span> <span m="3034950">be?</span> <span m="3036330">So</span> <span m="3036900">in</span> <span m="3037040">this</span> <span m="3037220">case,</span> <span m="3037410">we</span> <span m="3037540">had</span> <span m="3037595">the</span> <span m="3037650">partial</span> <span m="3038100">order</span> <span m="3038560">because</span> <span m="3039650">we</span> <span m="3039955">see</span> <span m="3040260">that</span> <span m="3040850">certain</span> <span m="3042040">items</span> <span m="3042530">cannot</span> <span m="3042780">be</span> <span m="3042910">compared,</span> <span m="3045350">but</span> <span m="3045550">what</span> <span m="3045770">happens</span> <span m="3046240">if</span> <span m="3046360">you</span> <span m="3046450">have</span> <span m="3046610">a</span> <span m="3046680">total</span> <span m="3047110">order?</span> </p>
<p><span m="3051040">For</span> <span m="3051090">example--</span> <span m="3051720">yeah.</span> <span m="3051770">Do</span> <span m="3051880">you</span> <span m="3052140">have</span> <span m="3052430">a--</span> </p>
<p><span m="3052720">AUDIENCE:</span> <span m="3053200">It</span> <span m="3053440">would</span> <span m="3053680">be</span> <span m="3054160">a</span> <span m="3054640">straight</span> <span m="3054880">line.</span> </p>
<p><span m="3055120">MARTEN VAN DIJK:</span> <span m="3055600">Yeah.</span> <span m="3056000">That's</span> <span m="3056170">correct.</span> <span m="3056670">It</span> <span m="3056810">will</span> <span m="3056950">be</span> <span m="3057080">straight</span> <span m="3057450">line.</span> <span m="3058330">And</span> <span m="3061140">it</span> <span m="3061380">will</span> <span m="3061480">look</span> <span m="3062100">something</span> <span m="3062530">like</span> <span m="3062780">this</span> <span m="3064100">and</span> <span m="3064240">it</span> <span m="3064540">keeps</span> <span m="3064810">on</span> <span m="3064910">going</span> <span m="3066070">and</span> <span m="3066340">over</span> <span m="3066650">here</span> <span m="3066910">also,</span> <span m="3068010">keeps</span> <span m="3068250">on</span> <span m="3068310">going</span> <span m="3068590">like</span> <span m="3068780">this.</span> <span m="3069420">So</span> <span m="3069480">it's</span> <span m="3069630">a</span> <span m="3069690">straight</span> <span m="3070050">line.</span> <span m="3070350">If</span> <span m="3070470">it's</span> <span m="3070640">a</span> <span m="3070690">finite</span> <span m="3071290">set,</span> <span m="3072000">we</span> <span m="3072130">have</span> <span m="3072300">a</span> <span m="3072370">finite</span> <span m="3073410">line,</span> <span m="3073510">so</span> <span m="3073830">just</span> <span m="3075660">a</span> <span m="3075750">finite</span> <span m="3076070">number</span> <span m="3076300">of</span> <span m="3076410">vertices,</span> <span m="3077070">but</span> <span m="3077520">otherwise,</span> <span m="3077920">it's</span> <span m="3078070">just</span> <span m="3078900">an</span> <span m="3079100">infinite</span> <span m="3079510">line</span> <span m="3079980">or</span> <span m="3080140">a</span> <span m="3080180">half</span> <span m="3080820">or</span> <span m="3081000">semi</span> <span m="3081170">infinite</span> <span m="3081650">line.</span> </p>
<p><span m="3082940">So</span> <span m="3084770">why</span> <span m="3084980">is</span> <span m="3085130">that?</span> <span m="3086510">with</span> <span m="3086920">every</span> <span m="3087280">two</span> <span m="3087630">elements,</span> <span m="3088090">it</span> <span m="3088180">can</span> <span m="3088300">be</span> <span m="3088410">compared</span> <span m="3088800">to</span> <span m="3088900">one</span> <span m="3089000">another,</span> <span m="3089350">so</span> <span m="3089430">you</span> <span m="3089570">can</span> <span m="3089790">rank</span> <span m="3090160">them</span> <span m="3090410">essentially</span> <span m="3091020">along</span> <span m="3091530">this</span> <span m="3091780">line.</span> <span m="3091925">So</span> <span m="3092070">if</span> <span m="3092180">you</span> <span m="3092270">think</span> <span m="3092490">about</span> <span m="3092720">the</span> <span m="3092810">integers</span> <span m="3093850">and</span> <span m="3093990">the</span> <span m="3094070">less</span> <span m="3094320">than</span> <span m="3094480">or</span> <span m="3094580">equal</span> <span m="3094860">to</span> <span m="3095030">relation,</span> <span m="3095980">well,</span> <span m="3096400">we</span> <span m="3096490">see</span> <span m="3096670">that</span> <span m="3096840">one</span> <span m="3097070">is</span> <span m="3097690">less</span> <span m="3097920">than</span> <span m="3098020">or</span> <span m="3098120">equal</span> <span m="3098230">to</span> <span m="3098370">2</span> <span m="3098605">and</span> <span m="3098840">2</span> <span m="3099000">is</span> <span m="3099130">less</span> <span m="3099330">than</span> <span m="3099375">or</span> <span m="3099420">equal</span> <span m="3099630">to</span> <span m="3099750">3</span> <span m="3100220">and</span> <span m="3100380">so</span> <span m="3100590">on.</span> <span m="3100750">So</span> <span m="3100870">they</span> <span m="3101050">all</span> <span m="3102160">are</span> <span m="3102890">put</span> <span m="3103580">in</span> <span m="3103820">Hesse</span> <span m="3104120">diagram</span> <span m="3104670">as</span> <span m="3104970">a</span> <span m="3105030">straight</span> <span m="3105430">line.</span> </p>
<p><span m="3106880">So</span> <span m="3106950">that's</span> <span m="3107100">is</span> <span m="3107230">very</span> <span m="3107450">special</span> <span m="3108640">order.</span> <span m="3109960">We</span> <span m="3110100">have</span> <span m="3110300">a</span> <span m="3110430">ranking</span> <span m="3111060">with</span> <span m="3111210">the</span> <span m="3111330">total</span> <span m="3111700">order</span> <span m="3112510">through</span> <span m="3112760">this</span> <span m="3112950">straight</span> <span m="3113300">line.</span> <span m="3115015">It</span> <span m="3115280">will</span> <span m="3115510">be</span> <span m="3115640">great</span> <span m="3116010">if</span> <span m="3116130">you</span> <span m="3116210">can</span> <span m="3116380">also</span> <span m="3116830">rank</span> <span m="3117160">the</span> <span m="3117280">elements</span> <span m="3117670">in</span> <span m="3117750">a</span> <span m="3117810">partial</span> <span m="3118270">order</span> <span m="3119240">and</span> <span m="3119430">that's</span> <span m="3119450">what</span> <span m="3119660">we're</span> <span m="3119850">going</span> <span m="3120070">to</span> <span m="3120170">talk</span> <span m="3120440">about</span> <span m="3120710">next.</span> <span m="3122950">We're</span> <span m="3123060">going</span> <span m="3123210">to</span> <span m="3123310">talk</span> <span m="3123580">about</span> <span m="3123750">the</span> <span m="3123920">topological</span> <span m="3124570">sort</span> <span m="3125260">of</span> <span m="3125640">a</span> <span m="3125760">poset.</span> <span m="3127030">And</span> <span m="3127190">what</span> <span m="3127320">it</span> <span m="3127420">really</span> <span m="3127670">means</span> <span m="3127980">is</span> <span m="3128460">that</span> <span m="3128625">we're</span> <span m="3128790">going</span> <span m="3129700">to</span> <span m="3130160">extend,</span> <span m="3130920">essentially</span> <span m="3131350">the</span> <span m="3131450">partial</span> <span m="3132020">order</span> <span m="3132610">toward</span> <span m="3132820">a</span> <span m="3133410">total</span> <span m="3133910">order.</span> <span m="3134850">And</span> <span m="3134890">by</span> <span m="3134990">doing</span> <span m="3135320">that,</span> <span m="3136430">we</span> <span m="3136500">will</span> <span m="3136720">manage</span> <span m="3137240">to</span> <span m="3137780">put</span> <span m="3137950">a</span> <span m="3138000">ranking</span> <span m="3138570">to</span> <span m="3138740">all</span> <span m="3138885">the</span> <span m="3139030">items.</span> </p>
<p><span m="3140860">Let</span> <span m="3140970">me</span> <span m="3141060">define</span> <span m="3142230">what's</span> <span m="3142460">happening</span> <span m="3142840">here.</span> <span m="3146500">So</span> <span m="3148532">this</span> <span m="3148920">is</span> <span m="3149240">about</span> <span m="3149580">equivalence</span> <span m="3150100">classes</span> <span m="3152240">and</span> <span m="3152430">you</span> <span m="3152520">remember</span> <span m="3152890">this.</span> <span m="3165550">So</span> <span m="3165750">what</span> <span m="3165920">is</span> <span m="3166830">a</span> <span m="3167070">topological</span> <span m="3167700">sort?</span> <span m="3169270">So</span> <span m="3169450">the</span> <span m="3169570">idea</span> <span m="3169840">is</span> <span m="3170110">that</span> <span m="3179940">if</span> <span m="3181210">the</span> <span m="3181270">total</span> <span m="3181590">order</span> <span m="3181780">is</span> <span m="3181920">consistent</span> <span m="3182620">with</span> <span m="3182940">a</span> <span m="3183050">partial</span> <span m="3183560">order,</span> <span m="3194110">then</span> <span m="3194600">it</span> <span m="3194790">is</span> <span m="3195010">called</span> <span m="3195800">a</span> <span m="3198290">topological</span> <span m="3198680">sort.</span> <span m="3199620">So</span> <span m="3199900">let</span> <span m="3200040">me</span> <span m="3200160">redefine</span> <span m="3200810">it</span> <span m="3200930">again</span> <span m="3202450">more</span> <span m="3202630">formally.</span> </p>
<p><span m="3214780">So</span> <span m="3215030">what</span> <span m="3215200">is</span> <span m="3215400">it?</span> <span m="3217580">A</span> <span m="3217700">topological</span> <span m="3218420">sort</span> <span m="3222560">of</span> <span m="3223700">a</span> <span m="3224670">poset</span> <span m="3227230">is</span> <span m="3227450">formally</span> <span m="3227910">defined</span> <span m="3228780">as</span> <span m="3232330">a</span> <span m="3232520">total</span> <span m="3232780">order.</span> <span m="3239270">It's</span> <span m="3239420">a</span> <span m="3239510">total</span> <span m="3239950">order</span> <span m="3241540">that</span> <span m="3241700">has</span> <span m="3241960">the</span> <span m="3242030">same</span> <span m="3242410">set</span> <span m="3242760">of</span> <span m="3244530">items</span> <span m="3244980">of</span> <span m="3245110">elements</span> <span m="3245570">A</span> <span m="3247560">but</span> <span m="3247740">has</span> <span m="3248000">a</span> <span m="3248060">different</span> <span m="3249900">relation</span> <span m="3251000">that</span> <span m="3251390">we</span> <span m="3251490">will</span> <span m="3251880">denote</span> <span m="3252165">by</span> <span m="3252920">a</span> <span m="3253040">subscript,</span> <span m="3253740">t.</span> <span m="3255110">And</span> <span m="3256730">this</span> <span m="3256950">is</span> <span m="3257050">such</span> <span m="3257410">that</span> <span m="3259050">well,</span> <span m="3261370">the</span> <span m="3261530">original</span> <span m="3262270">relation</span> <span m="3263280">is</span> <span m="3263510">contained</span> <span m="3265390">in</span> <span m="3266460">the</span> <span m="3266540">new</span> <span m="3266790">one.</span> <span m="3268320">Notice</span> <span m="3268710">that</span> <span m="3268890">these</span> <span m="3269250">also</span> <span m="3269520">denote</span> <span m="3269950">sets,</span> <span m="3270470">so</span> <span m="3270620">that's</span> <span m="3270820">why</span> <span m="3270940">I</span> <span m="3271000">can</span> <span m="3271180">write</span> <span m="3271390">it</span> <span m="3271490">like</span> <span m="3271700">this.</span> <span m="3271940">So</span> <span m="3272080">this</span> <span m="3272200">set</span> <span m="3273870">that</span> <span m="3273960">is</span> <span m="3274120">defined</span> <span m="3274610">by</span> <span m="3274730">this</span> <span m="3275940">relation</span> <span m="3277540">is</span> <span m="3277790">a</span> <span m="3277880">subset</span> <span m="3279040">of</span> <span m="3280270">this</span> <span m="3280470">relation.</span> </p>
<p><span m="3281430">So</span> <span m="3281515">it</span> <span m="3281600">simply</span> <span m="3281970">means</span> <span m="3282320">that</span> <span m="3282930">if</span> <span m="3283700">x</span> <span m="3284670">is</span> <span m="3284940">related</span> <span m="3285390">to</span> <span m="3285630">y,</span> <span m="3286420">then</span> <span m="3286580">it</span> <span m="3286690">also</span> <span m="3286950">implies</span> <span m="3287760">that</span> <span m="3288130">x</span> <span m="3288640">is</span> <span m="3288920">related</span> <span m="3290170">to</span> <span m="3291820">y</span> <span m="3292110">in</span> <span m="3292230">the</span> <span m="3292330">total</span> <span m="3292750">order.</span> <span m="3297080">So</span> <span m="3297980">we're</span> <span m="3298250">interested</span> <span m="3298870">in</span> <span m="3298930">figuring</span> <span m="3299320">out</span> <span m="3299460">where</span> <span m="3299600">we</span> <span m="3299740">can</span> <span m="3299880">find</span> <span m="3300190">such</span> <span m="3300410">a</span> <span m="3300470">topological</span> <span m="3301070">sort.</span> <span m="3301510">Is</span> <span m="3301640">it</span> <span m="3301770">always</span> <span m="3302100">possible</span> <span m="3302520">to</span> <span m="3302640">do</span> <span m="3302790">so?</span> <span m="3310430">Now</span> <span m="3310550">it</span> <span m="3310670">turns</span> <span m="3310790">out</span> <span m="3310960">that</span> <span m="3311030">every</span> <span m="3311350">finite</span> <span m="3316950">poset</span> <span m="3317870">actually</span> <span m="3318240">has</span> <span m="3318530">a</span> <span m="3318600">topological</span> <span m="3319250">sort</span> <span m="3319590">and</span> <span m="3319760">we're</span> <span m="3319930">going</span> <span m="3320100">to</span> <span m="3320210">prove</span> <span m="3320520">this.</span> <span m="3330400">How</span> <span m="3330440">do</span> <span m="3330540">we</span> <span m="3330650">do</span> <span m="3330830">that?</span> <span m="3331110">So</span> <span m="3331470">let</span> <span m="3331610">me</span> <span m="3331750">first</span> <span m="3332100">write</span> <span m="3332280">out</span> <span m="3333480">the</span> <span m="3333600">theorem.</span> </p>
<p><span m="3336570">The</span> <span m="3336670">theorem</span> <span m="3337000">is</span> <span m="3337400">that</span> <span m="3337750">every</span> <span m="3341070">finite</span> <span m="3343330">poset</span> <span m="3346230">has</span> <span m="3346840">a</span> <span m="3348460">topological</span> <span m="3351920">sort.</span> <span m="3353290">The</span> <span m="3353390">basic</span> <span m="3353800">idea</span> <span m="3354240">is</span> <span m="3354405">that</span> <span m="3355250">in</span> <span m="3355450">order</span> <span m="3355580">to</span> <span m="3355690">prove</span> <span m="3356000">this,</span> <span m="3356470">it's</span> <span m="3356670">that</span> <span m="3356820">we're</span> <span m="3356970">going</span> <span m="3357270">to</span> <span m="3357430">look</span> <span m="3357690">at</span> <span m="3357870">a</span> <span m="3358030">minimal</span> <span m="3358520">element</span> <span m="3359010">in</span> <span m="3359090">the</span> <span m="3359190">poset.</span> <span m="3360070">For</span> <span m="3360240">example,</span> <span m="3360450">in</span> <span m="3360520">the</span> <span m="3360640">diagram,</span> <span m="3361100">we</span> <span m="3361210">have</span> <span m="3361380">four</span> <span m="3361690">minimal</span> <span m="3362090">elements.</span> <span m="3363370">I</span> <span m="3363470">will</span> <span m="3363510">define</span> <span m="3363890">what</span> <span m="3364030">that</span> <span m="3364170">means.</span> <span m="3365280">The</span> <span m="3365440">left</span> <span m="3365810">sock</span> <span m="3366080">and</span> <span m="3366115">the</span> <span m="3366132">right</span> <span m="3366150">sock</span> <span m="3367090">and</span> <span m="3367210">the</span> <span m="3367330">underwear</span> <span m="3367920">and</span> <span m="3368160">the</span> <span m="3368230">shirt</span> <span m="3368480">are</span> <span m="3368730">all</span> <span m="3369110">at</span> <span m="3369240">the</span> <span m="3369360">top</span> <span m="3369560">of</span> <span m="3369700">the</span> <span m="3369790">Hesse</span> <span m="3370050">diagram.</span> <span m="3371360">Those</span> <span m="3371470">are</span> <span m="3371610">minimal</span> <span m="3371950">elements.</span> </p>
<p><span m="3373720">I</span> <span m="3373840">just</span> <span m="3374090">take</span> <span m="3374270">one</span> <span m="3374440">of</span> <span m="3374550">them,</span> <span m="3375300">take</span> <span m="3375520">it</span> <span m="3375660">out</span> <span m="3376100">of</span> <span m="3377360">the</span> <span m="3377470">poset</span> <span m="3378090">that</span> <span m="3378850">I'm</span> <span m="3379050">looking</span> <span m="3379360">at.</span> <span m="3380320">I</span> <span m="3380720">will</span> <span m="3380843">get</span> <span m="3380966">a</span> <span m="3381090">smaller</span> <span m="3381500">poset</span> <span m="3381940">and</span> <span m="3382010">recursively,</span> <span m="3383390">I'm</span> <span m="3383550">going</span> <span m="3383870">to</span> <span m="3384010">construct</span> <span m="3384580">my</span> <span m="3386010">total</span> <span m="3386440">order.</span> <span m="3386890">So</span> <span m="3386980">it's</span> <span m="3387050">a</span> <span m="3387140">total</span> <span m="3387500">order</span> <span m="3387780">on</span> <span m="3387880">a</span> <span m="3387960">smaller</span> <span m="3389920">poset</span> <span m="3390440">and</span> <span m="3390520">then</span> <span m="3390670">I</span> <span m="3390830">add</span> <span m="3391030">the</span> <span m="3391100">minimal</span> <span m="3391410">element</span> <span m="3391770">back</span> <span m="3391990">to</span> <span m="3392190">it</span> <span m="3392700">and</span> <span m="3392860">then</span> <span m="3392880">I</span> <span m="3392900">get</span> <span m="3393120">a</span> <span m="3393240">total</span> <span m="3393600">order</span> <span m="3393860">for</span> <span m="3394030">the</span> <span m="3394110">whole</span> <span m="3394350">thing.</span> <span m="3395490">So</span> <span m="3395530">essentially</span> <span m="3395910">I'm</span> <span m="3395960">going</span> <span m="3396150">to</span> <span m="3396270">use</span> <span m="3396440">induction</span> <span m="3397890">and</span> <span m="3398820">before</span> <span m="3399190">I</span> <span m="3399220">can</span> <span m="3399410">do</span> <span m="3399570">that,</span> <span m="3400170">I'm</span> <span m="3400360">going</span> <span m="3400640">to</span> <span m="3400770">first</span> <span m="3401780">talk</span> <span m="3402230">about</span> <span m="3402660">what</span> <span m="3402770">it</span> <span m="3402900">means</span> <span m="3404680">to</span> <span m="3404810">have</span> <span m="3404960">a</span> <span m="3405070">minimal</span> <span m="3405410">element</span> <span m="3405810">because</span> <span m="3406090">that's</span> <span m="3406270">what</span> <span m="3406400">we</span> <span m="3406530">need.</span> </p>
<p><span m="3407630">So</span> <span m="3407790">x</span> <span m="3408040">in</span> <span m="3408210">A</span> <span m="3409260">is</span> <span m="3409500">called</span> <span m="3409820">minimal</span> <span m="3414400">if</span> <span m="3416040">it's</span> <span m="3416330">not</span> <span m="3416560">true</span> <span m="3417160">that</span> <span m="3417410">there</span> <span m="3417630">exists</span> <span m="3418705">a</span> <span m="3418960">y</span> <span m="3419690">in</span> <span m="3419950">A,</span> <span m="3421250">which</span> <span m="3421480">is</span> <span m="3421620">different</span> <span m="3422020">from</span> <span m="3422260">x,</span> <span m="3423810">but</span> <span m="3424010">such</span> <span m="3424360">that</span> <span m="3427310">y</span> <span m="3427770">is</span> <span m="3429540">smaller</span> <span m="3430050">than</span> <span m="3430250">x.</span> <span m="3431610">So</span> <span m="3431930">there</span> <span m="3432530">exist</span> <span m="3432990">no</span> <span m="3433340">other</span> <span m="3433820">y</span> <span m="3434670">in</span> <span m="3434920">A</span> <span m="3435872">that</span> <span m="3436350">is</span> <span m="3436450">smaller</span> <span m="3436790">than</span> <span m="3436950">x.</span> <span m="3438380">Then</span> <span m="3438770">if</span> <span m="3438910">that's</span> <span m="3439120">true,</span> <span m="3439320">we</span> <span m="3439495">call</span> <span m="3439670">x</span> <span m="3439880">a</span> <span m="3439920">minimal</span> <span m="3440240">element.</span> <span m="3440560">And</span> <span m="3440880">in</span> <span m="3441090">the</span> <span m="3441180">same</span> <span m="3441510">way,</span> <span m="3442540">of</span> <span m="3442600">course,</span> <span m="3443040">we</span> <span m="3443060">can</span> <span m="3443240">talk</span> <span m="3443590">about</span> <span m="3444140">a</span> <span m="3445360">maximal</span> <span m="3445880">element.</span> <span m="3449720">It's</span> <span m="3449930">exactly</span> <span m="3450430">the</span> <span m="3450550">same,</span> <span m="3451560">but</span> <span m="3452510">at</span> <span m="3452660">the</span> <span m="3452800">very</span> <span m="3453050">end,</span> <span m="3455310">we</span> <span m="3455380">will</span> <span m="3455510">have</span> <span m="3455740">the</span> <span m="3455840">reverse,</span> <span m="3456570">so</span> <span m="3456730">x</span> <span m="3456970">is</span> <span m="3457070">related</span> <span m="3457410">to</span> <span m="3457530">y.</span> </p>
<p><span m="3460060">Now,</span> <span m="3460220">it</span> <span m="3460330">turns</span> <span m="3460650">out</span> <span m="3460780">that</span> <span m="3460920">not</span> <span m="3461080">every</span> <span m="3461410">poset</span> <span m="3461870">has</span> <span m="3462140">a</span> <span m="3462240">minimal</span> <span m="3462620">element,</span> <span m="3463260">actually.</span> <span m="3464440">So</span> <span m="3465430">as</span> <span m="3465680">an</span> <span m="3465760">example,</span> <span m="3467200">we</span> <span m="3467210">may</span> <span m="3467390">consider</span> <span m="3468750">the</span> <span m="3469150">integers,</span> <span m="3470310">the</span> <span m="3471130">negative</span> <span m="3471470">and</span> <span m="3471580">positive</span> <span m="3472000">numbers</span> <span m="3472540">and</span> <span m="3472980">then</span> <span m="3473390">less</span> <span m="3473640">than</span> <span m="3473820">or</span> <span m="3473920">equal</span> <span m="3474330">to</span> <span m="3475110">relation.</span> <span m="3476590">There</span> <span m="3476740">does</span> <span m="3476800">not</span> <span m="3477160">exist</span> <span m="3477550">a</span> <span m="3477675">minimal</span> <span m="3477800">element.</span> <span m="3478430">You</span> <span m="3478540">can</span> <span m="3478680">always</span> <span m="3479170">find</span> <span m="3479400">a</span> <span m="3479450">smaller</span> <span m="3479990">elements.</span> <span m="3480960">So</span> <span m="3481610">it's</span> <span m="3481790">not</span> <span m="3481930">really</span> <span m="3482200">true</span> <span m="3482600">that</span> <span m="3482770">every</span> <span m="3482870">poset</span> <span m="3483690">actually</span> <span m="3484030">has</span> <span m="3484270">a</span> <span m="3484430">minimal</span> <span m="3484700">element.</span> <span m="3485420">It</span> <span m="3485560">turns</span> <span m="3485890">out</span> <span m="3486120">though</span> <span m="3486680">that</span> <span m="3486850">in</span> <span m="3487010">a</span> <span m="3487080">finite</span> <span m="3487880">poset,</span> <span m="3488360">we</span> <span m="3488520">do</span> <span m="3488710">have</span> <span m="3488970">minimal</span> <span m="3489400">elements</span> <span m="3490240">and</span> <span m="3490330">then</span> <span m="3490440">we</span> <span m="3490500">can</span> <span m="3490680">start</span> <span m="3491920">doing</span> <span m="3492150">the</span> <span m="3492240">proof</span> <span m="3492760">by</span> <span m="3492950">induction.</span> </p>
<p><span m="3495020">So</span> <span m="3495160">let's</span> <span m="3495350">prove</span> <span m="3495670">this,</span> <span m="3496230">that</span> <span m="3496600">every</span> <span m="3496760">finite</span> <span m="3497560">poset</span> <span m="3499650">has</span> <span m="3499860">a</span> <span m="3499900">minimal</span> <span m="3501020">element.</span> <span m="3503090">So</span> <span m="3504410">let's</span> <span m="3504640">do</span> <span m="3504720">that</span> <span m="3504890">up</span> <span m="3505040">here.</span> <span m="3507620">Actually,</span> <span m="3508040">we</span> <span m="3508350">do</span> <span m="3508600">need</span> <span m="3508880">this</span> <span m="3509130">theorem</span> <span m="3509480">later</span> <span m="3509950">on.</span> <span m="3514650">So</span> <span m="3514820">let's</span> <span m="3515020">start</span> <span m="3515330">out</span> <span m="3515520">here.</span> <span m="3518070">So</span> <span m="3518250">the</span> <span m="3518550">limit</span> <span m="3518660">that</span> <span m="3518740">we</span> <span m="3518820">want</span> <span m="3519090">to</span> <span m="3519180">prove</span> <span m="3521460">is</span> <span m="3522730">that</span> <span m="3524000">every</span> <span m="3526270">finite</span> <span m="3527780">poset</span> <span m="3530400">has</span> <span m="3531510">a</span> <span m="3532010">minimal</span> <span m="3534380">element.</span> <span m="3535910">And</span> <span m="3536510">in</span> <span m="3536650">order</span> <span m="3536770">to</span> <span m="3536900">do</span> <span m="3537050">that,</span> <span m="3537260">we're</span> <span m="3537420">going</span> <span m="3537645">to</span> <span m="3537870">define</span> <span m="3538570">what</span> <span m="3538740">is</span> <span m="3538940">called</span> <span m="3539220">a</span> <span m="3539330">chain.</span> </p>
<p><span m="3541760">And</span> <span m="3542100">a</span> <span m="3542480">chain</span> <span m="3543660">is</span> <span m="3544000">this</span> <span m="3544170">sequence</span> <span m="3544680">of</span> <span m="3544850">elements</span> <span m="3545930">that</span> <span m="3546080">are</span> <span m="3546160">related</span> <span m="3546480">to</span> <span m="3546600">one</span> <span m="3546730">another.</span> <span m="3547100">It's</span> <span m="3547270">a</span> <span m="3547360">sequence</span> <span m="3551900">of</span> <span m="3552180">distinct</span> <span m="3552940">elements</span> <span m="3558160">such</span> <span m="3558640">that</span> <span m="3560670">a1</span> <span m="3561790">is</span> <span m="3561920">smaller</span> <span m="3562380">than</span> <span m="3562950">a2,</span> <span m="3564250">smaller</span> <span m="3564690">than</span> <span m="3564920">a3,</span> <span m="3566240">and</span> <span m="3566490">so</span> <span m="3566750">on</span> <span m="3567240">up</span> <span m="3567390">to</span> <span m="3567735">some</span> <span m="3568080">at.</span> <span m="3569470">And</span> <span m="3569650">the</span> <span m="3569710">length</span> <span m="3570030">of</span> <span m="3570180">a</span> <span m="3570250">chain</span> <span m="3570600">we</span> <span m="3570940">will</span> <span m="3571580">denote</span> <span m="3571970">by</span> <span m="3572110">t.</span> <span m="3572500">So</span> <span m="3572660">this</span> <span m="3572840">is</span> <span m="3572960">going</span> <span m="3573160">to</span> <span m="3573270">be</span> <span m="3573430">the</span> <span m="3574800">length.</span> </p>
<p><span m="3578980">So</span> <span m="3579160">now</span> <span m="3579350">let's</span> <span m="3579560">have</span> <span m="3579730">a</span> <span m="3579780">proof</span> <span m="3580080">of</span> <span m="3580170">this</span> <span m="3580350">lemma</span> <span m="3581020">and</span> <span m="3581190">with</span> <span m="3581310">that</span> <span m="3581440">lemma,</span> <span m="3581960">we</span> <span m="3582090">will</span> <span m="3582220">then</span> <span m="3582400">be</span> <span m="3582570">able</span> <span m="3582710">to</span> <span m="3582810">prove</span> <span m="3583060">the</span> <span m="3583140">theorem</span> <span m="3583600">that</span> <span m="3583730">we</span> <span m="3583850">want</span> <span m="3584410">to</span> <span m="3584580">do</span> <span m="3585100">on</span> <span m="3585290">the</span> <span m="3585380">topological</span> <span m="3586460">sort.</span> <span m="3594590">So</span> <span m="3597120">let's</span> <span m="3597230">see</span> <span m="3597380">how</span> <span m="3597530">we</span> <span m="3597630">can</span> <span m="3597770">do</span> <span m="3597930">this.</span> <span m="3599660">So</span> <span m="3600000">what's</span> <span m="3600280">the</span> <span m="3600380">proof</span> <span m="3600680">going</span> <span m="3601065">to</span> <span m="3601450">be?</span> <span m="3604440">Well,</span> <span m="3604880">you</span> <span m="3605000">want</span> <span m="3605150">to</span> <span m="3605250">construct</span> <span m="3606190">a</span> <span m="3606890">minimal</span> <span m="3607470">element</span> <span m="3607870">that</span> <span m="3608000">we</span> <span m="3608110">think</span> <span m="3608370">would</span> <span m="3608500">be</span> <span m="3608640">minimal</span> <span m="3609660">and</span> <span m="3609790">how</span> <span m="3609870">are</span> <span m="3609950">we</span> <span m="3610060">going</span> <span m="3610260">to</span> <span m="3610370">do</span> <span m="3610560">it?</span> <span m="3610700">We're</span> <span m="3611045">going</span> <span m="3611217">to</span> <span m="3611390">look</span> <span m="3611620">at</span> <span m="3611940">the</span> <span m="3612460">chain</span> <span m="3612890">that</span> <span m="3613060">has</span> <span m="3615540">the</span> <span m="3615910">largest</span> <span m="3616070">length,</span> <span m="3616420">the</span> <span m="3616490">maximum</span> <span m="3616910">length.</span> </p>
<p><span m="3618070">So</span> <span m="3622060">let</span> <span m="3622550">a1</span> <span m="3625720">related</span> <span m="3625970">to</span> <span m="3626230">a2</span> <span m="3626620">and</span> <span m="3626760">so</span> <span m="3626960">on</span> <span m="3627640">to</span> <span m="3627950">an</span> <span m="3629232">be</span> <span m="3631176">a</span> <span m="3632150">maximum</span> <span m="3633010">length</span> <span m="3634600">chain.</span> <span m="3636090">Now,</span> <span m="3636200">I'm</span> <span m="3636360">cheating</span> <span m="3636660">here</span> <span m="3636960">a</span> <span m="3636990">little</span> <span m="3637230">bit</span> <span m="3638710">because</span> <span m="3639530">how</span> <span m="3639700">do</span> <span m="3639810">I</span> <span m="3639900">know</span> <span m="3640130">that</span> <span m="3640600">such</span> <span m="3641080">a</span> <span m="3641220">chain</span> <span m="3641540">actually</span> <span m="3641870">exists?</span> <span m="3642890">Does</span> <span m="3643030">there</span> <span m="3643220">exist</span> <span m="3643620">a</span> <span m="3643720">maximum</span> <span m="3644130">length</span> <span m="3644370">chain?</span> <span m="3645770">So</span> <span m="3645920">that</span> <span m="3646760">you</span> <span m="3646870">may</span> <span m="3647020">want</span> <span m="3647150">to</span> <span m="3647240">think</span> <span m="3647480">about</span> <span m="3647890">it.</span> <span m="3648520">So</span> <span m="3648700">it</span> <span m="3648820">actually</span> <span m="3649160">does</span> <span m="3649360">exist</span> <span m="3652380">and</span> <span m="3653600">if</span> <span m="3653790">you</span> <span m="3653930">think</span> <span m="3654150">about</span> <span m="3654345">it</span> <span m="3654540">yourself,</span> <span m="3655030">then</span> <span m="3656440">you</span> <span m="3656600">will</span> <span m="3656790">actually</span> <span m="3658310">use</span> <span m="3658720">the</span> <span m="3658810">fact</span> <span m="3659070">that</span> <span m="3659330">we</span> <span m="3659460">use</span> <span m="3659850">a</span> <span m="3660020">finite</span> <span m="3660600">poset.</span> </p>
<p><span m="3661010">If</span> <span m="3661050">you</span> <span m="3661143">have</span> <span m="3661236">a</span> <span m="3661330">finite</span> <span m="3661710">number</span> <span m="3661900">of</span> <span m="3662010">elements,</span> <span m="3662985">well,</span> <span m="3663810">the</span> <span m="3663920">maximum</span> <span m="3664410">length</span> <span m="3664820">chain</span> <span m="3665160">can</span> <span m="3665300">be</span> <span m="3665410">at</span> <span m="3665530">most</span> <span m="3665860">the</span> <span m="3665890">number</span> <span m="3666100">of</span> <span m="3666220">elements</span> <span m="3666600">in</span> <span m="3666660">the</span> <span m="3666760">poset,</span> <span m="3667340">so</span> <span m="3668710">you</span> <span m="3668880">always</span> <span m="3669180">have</span> <span m="3669330">a</span> <span m="3669380">maximum</span> <span m="3670520">number,</span> <span m="3670910">but</span> <span m="3671070">you</span> <span m="3671160">can</span> <span m="3671380">prove</span> <span m="3671555">it</span> <span m="3671730">more</span> <span m="3671890">formally</span> <span m="3672370">by</span> <span m="3672720">using</span> <span m="3672840">the</span> <span m="3672900">well-ordering</span> <span m="3673300">principle.</span> <span m="3674730">But</span> <span m="3674860">I</span> <span m="3674950">will</span> <span m="3675030">not</span> <span m="3675170">do</span> <span m="3675250">that</span> <span m="3675450">here,</span> <span m="3675850">so</span> <span m="3678120">we</span> <span m="3678290">issue</span> <span m="3678690">for</span> <span m="3678850">now</span> <span m="3679030">that</span> <span m="3679160">this</span> <span m="3679350">just</span> <span m="3679550">exists,</span> <span m="3680140">but</span> <span m="3680290">you</span> <span m="3680360">can</span> <span m="3680500">prove</span> <span m="3680800">it.</span> </p>
<p><span m="3683110">So</span> <span m="3683330">let's</span> <span m="3683750">look</span> <span m="3683950">at</span> <span m="3684060">two</span> <span m="3684280">cases.</span> <span m="3687150">So</span> <span m="3687330">what</span> <span m="3687410">do</span> <span m="3687500">we</span> <span m="3687610">want</span> <span m="3687800">to</span> <span m="3687920">do?</span> <span m="3688160">We</span> <span m="3688190">want</span> <span m="3688330">to</span> <span m="3688410">show</span> <span m="3688680">that</span> <span m="3688850">a1</span> <span m="3689300">is</span> <span m="3689430">actually</span> <span m="3689780">minimum</span> <span m="3690170">element.</span> <span m="3691790">So</span> <span m="3692340">let</span> <span m="3692530">us</span> <span m="3692680">consider</span> <span m="3693130">any</span> <span m="3693430">other</span> <span m="3693670">element</span> <span m="3694100">in</span> <span m="3694175">the</span> <span m="3694250">set</span> <span m="3695130">and</span> <span m="3695780">then</span> <span m="3695930">we</span> <span m="3696200">have</span> <span m="3696300">two</span> <span m="3696400">case.</span> <span m="3697080">Either</span> <span m="3697500">a</span> <span m="3697790">is</span> <span m="3698080">actually</span> <span m="3699190">not</span> <span m="3699395">a</span> <span m="3699600">part</span> <span m="3700130">of</span> <span m="3700400">a1,</span> <span m="3701270">a2,</span> <span m="3702240">all</span> <span m="3702450">the</span> <span m="3702540">way</span> <span m="3702780">up</span> <span m="3702920">to</span> <span m="3703080">an.</span> </p>
<p><span m="3704850">Well,</span> <span m="3705020">in</span> <span m="3705100">that</span> <span m="3705270">case,</span> <span m="3707720">if</span> <span m="3708500">a</span> <span m="3709210">is</span> <span m="3709820">less</span> <span m="3710170">than</span> <span m="3710410">a1,</span> <span m="3711870">well,</span> <span m="3714370">what</span> <span m="3714530">goes</span> <span m="3714740">wrong?</span> <span m="3716180">I</span> <span m="3716340">can</span> <span m="3716540">put</span> <span m="3716790">a</span> <span m="3717380">up</span> <span m="3717700">front</span> <span m="3718140">here.</span> <span m="3718470">It's</span> <span m="3718500">a</span> <span m="3718530">different</span> <span m="3719150">element</span> <span m="3719490">from</span> <span m="3719590">all</span> <span m="3719700">the</span> <span m="3719810">others.</span> <span m="3720020">I</span> <span m="3720205">get</span> <span m="3720390">a</span> <span m="3720410">longer</span> <span m="3720800">chain.</span> <span m="3721890">So</span> <span m="3722480">that's</span> <span m="3722700">not</span> <span m="3722850">possible,</span> <span m="3723260">right?</span> <span m="3723480">So</span> <span m="3723680">we'll</span> <span m="3723830">get</span> <span m="3724550">a</span> <span m="3724700">longer</span> <span m="3726430">chain</span> <span m="3728760">and</span> <span m="3729020">that's</span> <span m="3729200">a</span> <span m="3729250">contradiction.</span> <span m="3730560">So</span> <span m="3730670">this</span> <span m="3730910">assumption</span> <span m="3731380">is</span> <span m="3731540">not</span> <span m="3731740">true.</span> <span m="3732060">So</span> <span m="3732150">it's</span> <span m="3732310">not</span> <span m="3732550">true</span> <span m="3733400">that</span> <span m="3733720">a</span> <span m="3734440">is</span> <span m="3734980">less</span> <span m="3735460">than</span> <span m="3735670">a1.</span> </p>
<p><span m="3740030">What's</span> <span m="3740320">the</span> <span m="3740440">other</span> <span m="3740650">case?</span> <span m="3742420">The</span> <span m="3742450">other</span> <span m="3742690">case</span> <span m="3743060">is</span> <span m="3743540">that</span> <span m="3743673">a</span> <span m="3743806">is</span> <span m="3743940">an</span> <span m="3744040">element</span> <span m="3744430">of</span> <span m="3744560">one</span> <span m="3744690">of</span> <span m="3744790">those.</span> <span m="3747000">So</span> <span m="3748840">it's</span> <span m="3749120">one</span> <span m="3749320">of</span> <span m="3749460">those</span> <span m="3752180">in</span> <span m="3752340">the</span> <span m="3752450">chain.</span> <span m="3755000">Now,</span> <span m="3755190">let's</span> <span m="3755480">have</span> <span m="3755580">a</span> <span m="3755640">look</span> <span m="3755830">what</span> <span m="3755950">happens</span> <span m="3756660">if</span> <span m="3757240">a</span> <span m="3757930">is</span> <span m="3758740">less</span> <span m="3759060">than</span> <span m="3759170">or</span> <span m="3759210">equal</span> <span m="3759490">to</span> <span m="3759720">a1.</span> <span m="3760930">But</span> <span m="3761090">wait</span> <span m="3761260">a</span> <span m="3761300">minute.</span> <span m="3761620">If</span> <span m="3761810">a</span> <span m="3763210">is</span> <span m="3763480">one</span> <span m="3763640">of</span> <span m="3763780">these</span> <span m="3765180">and</span> <span m="3766080">a</span> <span m="3766420">is</span> <span m="3766480">less</span> <span m="3766540">than</span> <span m="3766600">or</span> <span m="3766710">equal</span> <span m="3766890">to</span> <span m="3767070">a1,</span> <span m="3768100">then</span> <span m="3768370">I</span> <span m="3768470">will</span> <span m="3768600">have</span> <span m="3768840">a</span> <span m="3768910">cycle,</span> <span m="3769710">a1</span> <span m="3769850">is</span> <span m="3770220">less</span> <span m="3770326">than</span> <span m="3770433">or</span> <span m="3770540">equal</span> <span m="3771380">to</span> <span m="3771590">a</span> <span m="3772490">is</span> <span m="3772940">less</span> <span m="3773060">than</span> <span m="3773420">or</span> <span m="3773486">equal</span> <span m="3773553">to</span> <span m="3773620">a1,</span> <span m="3774120">but</span> <span m="3774260">you</span> <span m="3774360">just</span> <span m="3774780">showed</span> <span m="3775140">in</span> <span m="3775220">the</span> <span m="3775300">theorem</span> <span m="3776380">that</span> <span m="3776710">there</span> <span m="3776870">are</span> <span m="3776930">no</span> <span m="3777050">other</span> <span m="3777230">exit</span> <span m="3777520">cycles</span> <span m="3778440">in</span> <span m="3778610">a</span> <span m="3778680">poset,</span> <span m="3779990">so</span> <span m="3780110">this</span> <span m="3780370">would</span> <span m="3780510">imply</span> <span m="3783240">that</span> <span m="3783460">we</span> <span m="3783550">have</span> <span m="3783670">a</span> <span m="3783750">cycle.</span> <span m="3784670">And</span> <span m="3784820">according</span> <span m="3785140">to</span> <span m="3785250">the</span> <span m="3785350">theorem</span> <span m="3785655">up</span> <span m="3785960">there,</span> <span m="3786470">we</span> <span m="3786590">have</span> <span m="3786730">a</span> <span m="3786780">contradiction.</span> <span m="3787480">So</span> <span m="3787560">also</span> <span m="3788010">in</span> <span m="3788140">this</span> <span m="3788450">case</span> <span m="3788830">it's</span> <span m="3789030">not</span> <span m="3789250">true</span> <span m="3790220">that</span> <span m="3790490">a</span> <span m="3791310">is</span> <span m="3791570">less</span> <span m="3791850">than</span> <span m="3792180">a1.</span> </p>
<p><span m="3794080">Now</span> <span m="3794260">this</span> <span m="3794490">is</span> <span m="3794620">the</span> <span m="3794710">definition</span> <span m="3795560">of</span> <span m="3795795">a</span> <span m="3796030">minimal</span> <span m="3796370">elements.</span> <span m="3797150">So</span> <span m="3797230">let's</span> <span m="3797380">have</span> <span m="3797470">a</span> <span m="3797560">look</span> <span m="3797750">at</span> <span m="3798170">this</span> <span m="3798350">definition.</span> <span m="3798910">We</span> <span m="3799080">have</span> <span m="3799800">proof</span> <span m="3800230">now</span> <span m="3800450">that</span> <span m="3803350">for</span> <span m="3803660">every</span> <span m="3804170">possibility</span> <span m="3805870">every</span> <span m="3806160">possible</span> <span m="3806560">item</span> <span m="3806880">or</span> <span m="3807040">element</span> <span m="3807410">in</span> <span m="3807500">set</span> <span m="3807800">A,</span> <span m="3809910">it's</span> <span m="3810160">not</span> <span m="3810390">true</span> <span m="3814670">that</span> <span m="3814830">that</span> <span m="3815240">new</span> <span m="3815500">element</span> <span m="3815950">is</span> <span m="3816050">smaller</span> <span m="3816600">than</span> <span m="3818120">a1.</span> <span m="3819240">So</span> <span m="3819440">a1</span> <span m="3819750">is</span> <span m="3819880">actually</span> <span m="3820480">a</span> <span m="3820550">minimum</span> <span m="3821010">element</span> <span m="3822520">according</span> <span m="3822890">to</span> <span m="3823020">the</span> <span m="3823100">definition.</span> <span m="3823780">So</span> <span m="3824100">a1</span> <span m="3825210">is</span> <span m="3825490">minimal,</span> <span m="3825745">that's</span> <span m="3826000">what</span> <span m="3826430">we</span> <span m="3826860">have</span> <span m="3827290">shown.</span> <span m="3828640">So</span> <span m="3828890">great.</span> <span m="3829245">We</span> <span m="3829600">have</span> <span m="3829810">shown</span> <span m="3830840">that</span> <span m="3831190">there</span> <span m="3831330">exists</span> <span m="3831690">a</span> <span m="3831730">minimum</span> <span m="3832270">element,</span> <span m="3832555">so</span> <span m="3832840">this</span> <span m="3832900">is</span> <span m="3833190">the</span> <span m="3833300">end</span> <span m="3833500">of</span> <span m="3833640">this</span> <span m="3833880">proof.</span> </p>
</div>
        <div id="vid_related" itemprop="description" class="tabContent hide">
<h2 class="subhead">Free Downloads</h2>
<h3 class="subsubhead">Video</h3>
<ul>
<li>iTunes U (<a href="http://itunes.apple.com/us/itunes-u/lecture-11-relations-partial/id503873536?i=110644975">MP4 - 140MB</a>)</li>
<li>Internet Archive (<a href="http://www.archive.org/download/MIT6.042JF10/MIT6_042JF10_lec11_300k.mp4">MP4 - 140MB</a>)</li>
</ul>
<br>
<h3 class="subsubhead">Caption</h3>
<ul>
<li>English-US (<a href="../../../contents/video-lectures/lecture-11-relations-partial-orders-and-scheduling/1nScXLQAQ9A.srt">SRT</a>)</li>
</ul>
</div>
    
   </div>  




      					 
        <div class="" id="parent-fieldname-bottom_html_area">
            
            
        </div>
    
               </main><!--Course_inner_media tag close -->
           		</div>
<!--Course_wrapper tag close -->
            </div>
<!--left tag close -->
            <aside id="right">
                <!--Begin Right Portion -->
                    <div>
    



</div>

                	<div>
    



</div>


        <div class="" id="parent-fieldname-rsi_top_html_area">
            
            
        </div>
    

<!-- RSI google ad space-->



<div id="google_ads">    
    <script async="async" src="https://www.googletagservices.com/tag/js/gpt.js"></script>
    <script type="text/javascript">var googletag = googletag || {}; googletag.cmd = googletag.cmd || [];</script>
    <script type="text/javascript">
googletag.cmd.push(function() {googletag.defineSlot('/1064917/VIDEO_INDIVIDUAL_SLOT_A_DL', [[300, 250], [300, 300], [180, 200], [180, 150], [160, 600]], 'VIDEO_INDIVIDUAL_SLOT_A_DL').addService(googletag.pubads());googletag.defineSlot('/1064917/VIDEO_INDIVIDUAL_SLOT_B_DL', [[300, 250], [300, 300], [180, 200], [180, 150], [160, 600]], 'VIDEO_INDIVIDUAL_SLOT_B_DL').addService(googletag.pubads());googletag.defineSlot('/1064917/VIDEO_INDIVIDUAL_SLOT_C_DL', [[300, 250], [300, 300], [180, 200], [180, 150], [160, 600]], 'VIDEO_INDIVIDUAL_SLOT_C_DL').addService(googletag.pubads());
googletag.pubads().enableSingleRequest();
 googletag.enableServices();
});</script>
    <script language="javascript" type="text/javascript">
googletag.cmd.push(function() {googletag.pubads().set("TYPE","HOUSE");googletag.pubads().set("DEPARTMENT","6");googletag.pubads().set("CRS_BEG2","04");googletag.pubads().set("CRS_END","2J");googletag.pubads().set("SESSION","F");googletag.pubads().set("YEAR","10");})
</script>
    
    <div id="VIDEO_INDIVIDUAL_SLOT_A_DL">
    	<script>googletag.cmd.push(function() { googletag.display('VIDEO_INDIVIDUAL_SLOT_A_DL'); });</script>
    </div>
    <div id="VIDEO_INDIVIDUAL_SLOT_B_DL">
    	<script>googletag.cmd.push(function() { googletag.display('VIDEO_INDIVIDUAL_SLOT_B_DL'); });</script>
    </div>
    <div id="VIDEO_INDIVIDUAL_SLOT_C_DL">
    	<script>googletag.cmd.push(function() { googletag.display('VIDEO_INDIVIDUAL_SLOT_C_DL'); });</script>
    </div>
</div>

<!-- End RSI ads--> 


<div>
    



</div>

            </aside><!--Right div close -->
            <div class="clear"></div>
        </div>
<!--grid tag close -->
      </div>
		
		<footer id="bottom">
			<div id="grid">
				
<div id="portletwrapper-6f63772e626f74746f6d706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a736974652d666f6f746572" class="portletWrapper kssattr-portlethash-6f63772e626f74746f6d706f72746c65746d616e616765720a636f6e746578740a2f506c6f6e650a736974652d666f6f746572">
<div class="portletStaticText portlet-static-site-footer"><div id="footer">
<nav aria-label="Footer">     <nav id="foot-c1" class="grid_2 alpha" aria-labelledby="f-find-courses">       <span class="footer" id="f-find-courses" aria-hidden="true">Find Courses</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://ocw.mit.edu/courses/find-by-topic/">Find by Topic</a></li>
    <li><a href="https://ocw.mit.edu/courses/find-by-number/">Find by Course Number</a></li>
    <li><a href="https://ocw.mit.edu/courses/find-by-department/">Find by Department</a></li>
    <li><a href="https://ocw.mit.edu/courses/new-courses/">New Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/most-visited-courses/">Most Visited Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/ocw-scholar/">OCW Scholar Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/audio-video-courses/">Audio/Video Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/online-textbooks/">Online Textbooks</a></li>
    <li><a href="https://ocw.mit.edu/courses/instructor-insights/">Instructor Insights</a></li>
    <li><a href="https://ocw.mit.edu/resources/">Supplemental Resources</a></li>
    <li><a href="https://ocw.mit.edu/courses/mitx-related-courseware/">MITx &amp; Related OCW Courses</a></li>
    <li><a href="https://ocw.mit.edu/courses/mit-open-learning-library/">MIT Open Learning Library</a></li>
    <li><a href="https://ocw.mit.edu/courses/translated-courses/">Translated Courses</a></li>
</ul>
</nav>
<div id="foot-c2" class="grid_2"><nav aria-labelledby="f-for-educators">         <span id="f-for-educators" class="footer" aria-hidden="true">For Educators</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://chalk-radio.simplecast.com/">Chalk Radio Podcast</a></li>
    <li><a href="https://ocw.mit.edu/educator/">OCW Educator Portal </a></li>
    <li><a href="https://ocw.mit.edu/courses/instructor-insights/">Instructor Insights by Department</a></li>
    <li><a href="https://openlearning.mit.edu/campus/digital-innovations/" aria-label="External Link: Residential Digital Innovations">Residential Digital Innovations </a></li>
    <li><a href="https://ocw.mit.edu/high-school/">OCW Highlights for High School</a></li>
    <li><a href="https://ocw.mit.edu/educator/additional-resources/">Additional Resources</a></li>
</ul>
</nav></div>
<nav class="grid_2" id="foot-c3" aria-labelledby="f-donate">       <span id="f-donate" class="footer" aria-hidden="true">Give Now</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://ocw.mit.edu/give/">Make a Donation</a></li>
    <li><a href="https://ocw.mit.edu/give/why-give/">Why Give?</a></li>
    <li><a href="https://ocw.mit.edu/give/our-supporters/">Our Supporters</a></li>
    <li><a href="https://ocw.mit.edu/give/other-ways-to-contribute/">Other Ways to Contribute</a></li>
    <li><a href="https://ocw.mit.edu/support/">Become a Corporate Sponsor</a></li>
</ul>
</nav>
<div class="grid_2" id="foot-c4">
<nav aria-labelledby="f-about">         <span id="f-about" class="footer" aria-hidden="true">About</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://ocw.mit.edu/about/">About OpenCourseWare</a></li>
    <li><a href="https://ocw.mit.edu/about/site-statistics/">Site Statistics</a></li>
    <li><a href="https://ocw.mit.edu/about/ocw-stories/">OCW Stories</a></li>
    <li><a href="https://ocw.mit.edu/about/newsletter/">Newsletter</a></li>
    <li><a href="https://www.ocw-openmatters.org/">Open Matters Blog</a></li>
</ul>
</nav><!--about-->       <nav aria-labelledby="f-tools">         <span id="f-tools" class="footer" aria-hidden="true">Tools</span>
<ul class="foot-bullet" role="presentation">
    <li><a href="https://ocw.mit.edu/help/">Help &amp; FAQs</a></li>
    <li><a href="https://ocw.mit.edu/about/contactus">Contact Us</a></li>
    <li><a href="https://accessibility.mit.edu/" target="_blank">Accessibility</a></li>
    <li><a href="https://ocw.mit.edu/help/site-map/">Site Map</a></li>
    <li><a href="../../../common/terms/index.htm">Privacy &amp; Terms of Use</a></li>
    <li><a href="https://ocw.mit.edu/help/rss/">RSS Feeds</a></li>
</ul>
</nav><!--tools-->
</div>
</nav> <aside style="min-height: 289px;" aria-labelledby="f-our-corporate-supporters" class="grid_4 omega" id="foot-c5">           <span aria-hidden="true" class="footer" id="f-our-corporate-supporters">Our Corporate Supporters</span>           <!-- HOME_CORP_LOGO_1 -->
<div id="div-gpt-ad-1388181177156-0" class="sponsors_google_ads_even"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-0'); });
            </script></div>
<!-- HOME_CORP_LOGO_2 -->
<div id="div-gpt-ad-1388181177156-1" class="sponsors_google_ads_odd"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-1'); });
            </script></div>
<!-- HOME_CORP_LOGO_3 -->
<div id="div-gpt-ad-1388181177156-2" class="sponsors_google_ads_even"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-2'); });
            </script></div>
<!-- HOME_CORP_LOGO_4 -->
<div id="div-gpt-ad-1388181177156-3" class="sponsors_google_ads_odd"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-3'); });
            </script></div>
<!-- HOME_CORP_LOGO_5 -->
<div id="div-gpt-ad-1388181177156-4" class="sponsors_google_ads_even"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-4'); });
              </script></div>
<!-- HOME_CORP_LOGO_6 -->
<div id="div-gpt-ad-1388181177156-5" class="sponsors_google_ads_odd"><script type="text/javascript">
              googletag.cmd.push(function() { googletag.display('div-gpt-ad-1388181177156-5'); });
              </script></div>
</aside>
<div class="grid_12 alpha omega" itemprop="publisher" itemscope="" itemtype="http://schema.org/CollegeOrUniversity">
<h4 class="footer" style="border-top: thin solid #d5c9ba; padding-top: 10px; margin-bottom: 10px;">About <span itemprop="name">MIT OpenCourseWare</span>
</h4>
<p style="color: #999; font-size: 1em; line-height: 1.5em; margin-top: 10px;" itemprop="description">MIT OpenCourseWare is an online publication of materials from over 2,500 MIT courses, freely sharing knowledge with learners and educators around the world. <a href="https://ocw.mit.edu/about/">Learn more »</a></p>
</div>
<div id="foot-copy" class="grid_12 alpha omega" style="border-top: none;">
<a href="http://web.mit.edu"><img src="../../../common/images/logo_mit.png" alt="Massachusetts Institute of Technology logo and name." style="width: 195; height: 44;"></a><a href="https://openlearning.mit.edu/"><img src="https://ocw.mit.edu/images/mitol_logo.png" alt="MIT Open Learning logo and name." style="width: 265; height: 50; vertical-align: top; padding-left:30px;"></a><a href="https://www.oeglobal.org/"><img src="https://ocw.mit.edu/images/oeg_logo.gif" alt="Open Education Consortium logo." style="width: 219px; height: 59px; vertical-align: top; padding-left:20px;"></a><a rel="license" itemprop="useRightsUrl" href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><img src="../../../common/images/cc_by-nc-sa.png" alt="Creative Commons logo with terms BY-NC-SA." style="width: 126px; height: 44px; margin-right: 0; padding-left: 20px;"></a>
<p class="copyright">© 2001–2018<br>
Massachusetts Institute of Technology</p>
<p style="font-size: 0.9em; margin-bottom: 15px;">Your use of the MIT OpenCourseWare site and materials is subject to our <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="license">Creative Commons License</a> and other <a href="../../../common/terms/index.htm" rel="cc:morePermissions">terms of use</a>.</p>
</div>
</div></div>

</div>





                
			</div> <!-- bottom grid end -->
		</footer><!-- footer bottom end -->


   </body>
 </html>
